Основы численных методов решения задач

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

· исходные данные могут изменяться в определенных пределах – массовость алгоритма;

· процесс применения правил к исходным данным (путь решения задачи) определен однозначно – детерменированность алгоритма;

· на каждом шаге процесса применения правил известно, что считать результатом этого процесса – результативность алгоритма.

Для примера рассмотрим алгоритмы решения уравнений.

Пусть дана непрерывная функция f(x) и требуется найти корень уравнения f(x) = 0. Предположим, что найден отрезок [ a, b ], такой, что f(a)f(b) < 0. Тогда согласно теореме Больцано – Коши[*] внутри отрезка [ a, b ] существует точка с, в которой значение функции равно нулю.

Метод вилки, или метод бисекций, заключается в построении последовательно вложенных друг в друга отрезков, на концах которых функция принимает значения разных знаков. Каждый последующий отрезок получают делением пополам предыдущего. Процесс построения последовательности отрезков позволяет найти нуль функции f(x) с любой заданной точностью.

Опишем один шаг итераций.

Пусть на (n – 1) шаге найден отрезок [ a ₍ _n _{– 1)}, b ₍ _n _{– 1)}] Ì [ a, b ], такой, что

f(a ₍ _n _{– 1)})f(b ₍ _n _{– 1)}) < 0.

Делим его пополам точкой с = (a ₍ _n _{– 1)}+ b ₍ _n _{– 1)})/2 и вычисляем f(c). Если f(c) = 0, то с – корень уравнения. Если f(c) ¹ 0, то из двух половин отрезка выберем ту, на концах которой значения функции имеют противоположные знаки и один из корней функции лежит на этой половине.

Таким образом,

a_n = a _{(n – 1)}, b_n = c, если f(c)f(a _{(n –1)}) < 0,

a_n = c, b_n = b _{(n – 1)}, если f(с)f(a _{(n –1)}) > 0.

Если требуется найти корень с точностью e, то деление продолжается до тех пор, пока длина отрезка не станет меньше 2e. Тогда координата середины отрезка и есть значение корня с требуемой точностью.

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

где .

Если на отрезке [ a, b ] находится несколько корней уравнения, то метод позволяет определить только один из них.

Метод простых итераций (последовательных приближений) решения уравнения f(x) = 0 состоит в замене исходного уравнения эквивалентным ему уравнением x = j(x) и построении последовательности x ₍ _n _{+ 1)}= j(x_n), сводящейся при n ® ¥ к точному решению. Сформулируем достаточные условия сводимости метода простых итераций.

Теорема. Пусть функция j(x) определена и дифференцируема на [a, b], причем все ее значения j(x)Ì [a, b]. Тогда, если существует число q, такое, что / j’(x) / £ q < 1 на отрезке [a, b], то последовательность x₍_n _{+ 1)}=j(x_n),

n = 0, 1, 2,..., сводится к единственному на [a, b] решению уравнения x = j(x) при любом начальном значении x₀Ì [a, b], т. е.

, f(c) = 0, c Ì [ a, b ].

При этом если на отрезке [a, b] производная j’(x) положительна, то

если j’(x) отрицательна, то

Опишем один шаг итераций. Исходя из найденного на предыдущем шаге значения x ₍ _n _{– 1)}, вычисляем y = j(x ₍ _n _{– 1)}).

Если | y – x ₍ _n _{– 1)}| > e, полагают x_n = y и выполняют очередную итерацию. Если же значение | y – x ₍ _n _{– 1)}| < e, то вычисления заканчивают и за приближенное значение корня принимают величину x_n = y. Погрешность полученного результата зависит от знака производной j’(x). При j’(x) > 0 корень найден с погрешностью , если j’(x) < 0, то погрешность не превышает e.

Метод допускает прямую геометрическую интерпретацию. Построим графики функций y = x и y = j(x), Корнем с уравнения x = j(x) является абсцисса точки пересечения кривой y = j(x) с прямой y = x (рис. 2.1).

Рис. 2.1. Метод простых итераций

Взяв в качестве начальной произвольную точку x ₀Ì [ a, b ], строим ломаную линию. Абсциссы вершин этой ломаной представляют собой последовательные приближения корня с. Скорость сходимости к корню с тем выше, чем меньше число q.

Приближенное решение уравнения f(x) = 0 методом Ньютона или методом касательных заключается в построении итерационной последовательности x ₍ _n _{+ 1)} = x_n – f(x_n)/f’(x_n), сводящейся к корню уравнения f(x) = 0.

Сформулируем достаточные условия сходимости метода.

Теорема. Пусть f(x) определена и дважды дифференцируема на [a, b], причем f(a)f(b)< 0, а производные f’(x), f”(x) сохраняют знак на отрезке [a, b]. Тогда, исходя из начального приближения x₀Ì [a, b], удовлетворяющего неравенству f(x₀)f”(x₀) > 0, можно построить последовательность

x₍_n₊₁₎ = x_n – f(x_n)/f’(x_n), n = 0, 1, 2, …, сходящуюся к единственному на [a, b] решению уравнения f(x).

Метод Ньютона допускает простую геометрическую интерпретацию. Если через точку с координатами (x_n, f(x_n)) (рис. 2.2) провести касательную, то абсцисса точки пересечения этой касательной с осью Ох и есть очередное приближение x ₍ _n ₊₁₎корня уравнения f(x) = 0.

Рис. 2.2. Метод касательных

Если необходимо найти корень с точностью e, то итерационный процесс можно остановить, когда

где: m ₁ – наименьшее значение модуля первой производной |f’(x)| на [ a, b ],

M ₂ – наибольшее значение модуля второй производной |f”(x)| на отрезке [ a, b ].

Опишем один шаг итераций.

Если на (n – 1) шаге очередное приближение x ₍ _n _{– 1)} не удовлетворяет условию окончания процесса, то вычисляем величины f(x ₍ _n _{– 1)}), f’(x ₍ _n _{– 1)}) и следующее приближение корня x_n = x ₍ _n _{– 1)} – f(x ₍ _n _{– 1)})/f’(x ₍ _n _{– 1)}).