Тема: Численные методы нахождение корней алгебраических и трансцендентных уравнений

План: Нахождение корней алгебраических и трансцендентных уравнений при решении уравнений тепло - и массообмена. Методы нахождения корней уравнений: дихотомии, хорд, Ньютона, секущих, последовательных приближений.

5.1 Нахождение корней алгебраических и трансцендентных уравнений при решении задач тепло - и массообмена.

В научной и инженерской практике часто приходится решать алгебраические уравнения. Так при решении задачи нестационарной теплопроводности по определению температурного поля в бесконечной пластине толщиной 2δ было получено уравнение вида

Θ=Σ(2Θ₀sinμ_n/(μ_n+ sinμ_nсosμ_n)) сos(μ_nх/δ)exp(-μ_n²Fo),

в котором μ_n являлось корнем характеристического трансцендентного уравнения

μ_n/Bi=ctg μ_n.

Критериальные уравнения тепломассообмена, многие уравнения гидродинамики относятся к трансцендентным уравнениям [14-17].

Скорость и эффективность решений таких уравнений существенно влияют на применимость вычислительного процесса и определяются классом задачи. Алгебраические задачи могут быть классифицированы по числу уравнений, типу и количеству решений.

Рисунок 5.1 –Схема классификации алгебраических уравнений

Методы решения алгебраических уравнений делятся на прямые и итерационные.

Прямые это – например, нахождение корня квадратного уравнения.

В итерационных методах процедура решения задаётся в виде многократного применения некоторого алгоритма.

При решении таких задач предполагается, что корни являются действительными.

Отыскание корней уравнения состоит обычно из двух этапов. На первом этапе необходимо выяснить существуют ли решения, какого их количество, оценить примерное значение, оценить количество и величину интервалов, на котором функция меняет знак. Второй этап – нахождение корня в заданном интервале.

При решении задачи нахождения корней функции одной переменной вида f(x)=0, где f(x) – алгебраическая или трансцендентная функция, можно говорить только о приближенном вычислении корней уравнения, т. е. таких значений аргумента x=х^*, при которых выполняется равенство f(х^*)=0 с заданной точностью. Рассмотрим некоторые методы решения задач такого типа.

Метод половинного деления (дихотомия)

Дихотомия применяется, когда требуется надежность счета, а скорость сходимости не имеет значения.

f(х_n+1)

Y

f(х_ср)

х_n х_cр2 х^* х_cр1 х_n+1 Х

f(х_n)

Рисунок 5.2 – Геометрическая интерпретация метода дихотомии

Пусть дано уравнение f(x)=0 и отделен простой корень х^*, то есть найден такой отрезок [х_n, х_n+1], х^* принадлежит [х_n, х_n+1] и на концах интервала функция имеет значения, противоположные по знаку. Отрезок

[х_n, х_n+1] называется начальным интервалом неопределенности,потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.

Алгоритм метода дихотомии.

1. Вычисляют значения функции через равные интервалы значений х до смены знака, при переходе от f(x_n) к f(x_n+1)

2. Вычисляют среднее значение аргумента x_ср и находят f(x_ср).

3. Если знак f(x_ср) совпадает со знаком f(x_n), то в дальнейших расчетах вместо x_n используют x_cp. Если f(x_cp) совпадает с f(x_n+1), то вместо x_n+1 берут x_cp.

4. Интервал, в котором заключено значение корня, сужается. Если f(x_cpk) ≤ 0 + ε, где ε положительное наперед заданное достаточное малое число – точность расчета, то процесс заканчивается за k итераций, при этом ширина интервала уменьшается в 2^k раз. Если f(x_cpk) > 0 + ε, повторяют пп.2-3 алгоритма.

Метод имеет линейную, но безусловную сходимость, и его погрешность за каждую итерацию уменьшается в два раза.

Метод не применим к корням четной кратности, т.е. тогда когда, f(x)=g(x)(x-x₁)^m, где x₁ корень кратности m.

Метод хорд

В основе этого метода, как и в методе дихотомии, лежит линейная интерполяция по двум значениям функции, имеющим противоположные знаки, но он обеспечивает более быстрое нахождение корня.

Y f(х_n+1)

x₁^* x₂^* x₃^* x₄^* x^*

х_n х_n+1 X

f(х_n)

Рисунок 5.3 – Геометрическая интерпретация метода хорд

Алгоритм метода хорд.

1. Вычисляют значения функции через равные интервалы значений х до смены знака при переходе от f (x_n) к f (x_n+1).

2. Прямая, проходящая через эти две точки, пересекает ось х в точке

х^* = x_n – f (x_n)( x_n+1 - x_n)/ (f (x_n+1) – f (x_n)) (5.1)

3. Находят значение f (x_k^*), которое сравнивают с известными f (x_n),

f (x_n+1). Если знак f(x_к^*) совпадает со знаком f(x_n), то в дальнейших расчетах вместо x_n используют x_k^*. Если f(x_k^*) совпадает с f(x_n+1), то вместо x_n+1 берут x_k^*.

4. Проверяют близость f(x_k^*) к нулю c заданной точностью ε. Если f(x_k^*) ≤ 0 + ε, то процесс заканчивается за k итераций. Если f(x_k^*) > 0 + ε, повторяют пп.2-3 алгоритма.

В знаменателе формулы (5.1) стоит разность значений функций. Вдали от корня она несущественна, но вблизи корня эти значения близки и малы. Возникает потеря значащих цифр, приводящая к «разболтке» счета. Это ограничивает точность, с которой можно найти корень. Для простых корней это ограничение невелико, а для кратных – существенно. Можно использовать метод Гарвика. Выбирают не очень малое ε, ведут итерации до выполнения условия |x_n+1 - x_n| < ε и затем продолжают расчет до тех пор, пока |x_n+1 - x_n| убавает.

Метод Ньютона

Метод последовательных приближений, разработанный Ньютоном, используется наиболее часто среди всех итерационных алгоритмов.

Функция f(x), дважды дифференцируемая на отрезке [a, b], который содержит корень х^*. При этом f(x^*)=0. Для определения интервала, в котором заключен корень, в методе Ньютона не требуется находить значения функции с противоположными знаками. Вместо интерполяции по двум значениям функции будем проводить экстраполяцию с помощью касательной в данной точке.

Y

М₀

х^*

X

х₁ х₂ х₀

М₁

Рисунок 5.4 – Геометрическая интерпретация метода Ньютона

Алгоритм метода:

1. Находят значение x_n+1, которое соответствует точке, в которой касательная к кривой в точке x_n пересекает ось х

x_n+1 = x_n - f(x_n)/f ′(x_n) (5.2)

2. Процедуру повторяют до выполнения условия близости функции к нулю с заданной точностью f(x_n) ≈ ε

Быстрота сходимости метода Ньютона в большой мере зависит от выбора исходной точки. Если в процессе итераций тангенс угла наклона касательной f ′(x_n) обращается в ноль, то применение метода усложняется. В случае бесконечно больших f ′′(x) метод также недостаточно эффективен. При кратности корней (условие f (x)=f ′(x)=0) метод Ньютона не обеспечивает сходимости.

Метод секущих

Одним из недостатков метода Ньютона является необходимость дифференцирования заданной функции f(x). Если нахождение производной затруднено, можно воспользоваться некоторым приближением, которое положено в основу метода секущих. Заменим производную f ′(x_n) для расчета

x_n+1 = x_n - f(x_n)/f ′(x_n) разностью последовательных значений функции, отнесенных к разности последовательных значений аргумента, т.е. разделенной разностью первого порядка

F*(x_n)= (f(x_n)- f(x_n-1))/( x_n- x_n-1),

тогда

x_n+1 = x_n - f(x_n)/ F*(x_n). (5.3)

Схема алгоритма остается, как и в методе Ньютона, изменяется только вид итерационной формулы (5.3).

5.6 Метод простой итерации (последовательных приближений)

Для применения этого метода уравнение f(x)=0 приводится к виду

х = g(х). Задаются начальным значением х₀, а последующие приближения вычисляются с помощью итерационной процедуры

x_n+1= g(х_n). (5.4)

Для сходимости метода необходимо выполнение условия

0< g′ (х_n)<1

Y

x

g(x)

X

х₀ х₁ х₂

Рисунок 5.5 – Геометрическая интерпретация метода простых итераций

Компьютерная реализация методов в Excel описана в [9], [23-24, 26].

Литература: [1-4],[6], [9], [14-17], [23-24].

Лекция 6