Лабораторная работа № 14 Численные методы решения алгебраических уравнений

Теоретические сведения

Пусть дано уравнение f(x)=0, функция f(x) непрерывна на интервале [a,b]. Условие f(a) f(b)<0 указывает тогда на наличие хотя бы одного корня на этом отрезке. Наглядное отделение корней возможно при построении графика f(x) (рис.1).

Рис.1. Иллюстрация численного метода

Метод деления отрезка пополам (дихотомия)

Поделим отрезок [a,b] пополам точкой c, координата которой c=(a+b)/2 и вычислим значение функции f(c).

Возможны два случая:

а) f(a) f(c)>0, т.е. значения функции на концах отрезка [a, c] одинаковы по знаку; тогда корень уравнения находится на отрезке [c, b] и отрезок [a, c] можно исключить из дальнейшего рассмотрения, перенеся точку a в точку c: a=c; f(a)=f(c) (рис. 1а);

б) f(a) f(c)<0, т.е. значение функции на концах отрезка [a, c] противоположны по знаку; тогда корень находится на отрезке [a, c] и отрезок [c, b] можно исключить из дальнейшего рассмотрения, перенеся точку b в точку c: b=c (рис. 1б).

После исключения правой или левой половины отрезка продолжают деление пополам до тех пор, пока длина оставшегося интервала [a, b] не станет меньше некоторой заданной малой величины  , т.е.  b-a < , и тогда любое значение аргумента из отрезка [a, b] можно считать корнем с погрешностью  . Обычно принимают в качестве корня середину отрезка. Отметим, что  здесь имеет смысл допустимой абсолютной погрешности вычисления корня.

Достоинством метода является его безусловная сходимость, если на интервале [a, b] имеется хотя бы один корень. Кроме того, метод не использует производных. К недостаткам относят медленную сходимость, т.е. достаточно большое число вычислений функции f(x) по сравнению с другими методами. Рекомендуется к использованию в тех случаях, если нет жестких требований ко времени счета.

Рис. 2 Представление корня уравнения

а- математическое; б- машинное

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

Рис. 3 Графический метод решения алгебраического уравнения в Excel

Замечание. Если отрезок [a,b] делить в пропорции «золотого сечения» , то численный метод решения уравнения называется методом золотого сечения.

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

а б

Рис.4 Геометрическая иллюстрация

метода последовательных приближений при

а- ; б-

Задаем начальное значение аргумента . Циклически пересчитываем аргумент по формуле пока не достигнем заданной точности, т.е.

Рис.5 Расходимость метода итераций при

Метод касательных (метод Ньютона)

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

Рис. 6 Геометрическая иллюстрация метода касательных

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

В методе касательных производная функции заменяется конечной разностью .

Рис. 7 Геометрия метода секущих

Метод сканирования

Сканируем отрезок [a,b] с малым шагом, пока не попадем в малую окрестность решения, т.е. не достигнем заданной точности: .

Метод Монте-Карло

На отрезке [a,b] генерируем большую выборку случайных чисел. При этом возможно попадание случайной точки в малую окрестность решения уравнения, т.е. выполнение условия . Если уравнение имеет несколько корней, то программа запускается несколько раз.

Демонстрационные примеры численных методов на языке VBA

Function F(x As Variant) As Variant

F = 2 * x ^ 2 - 5 * x + 2

End Function

Sub Polovina() ‘метод половинного деления

n = 50

a = 0

b = 0.6

For i = 1 To n

x = (b + a) / 2

If F(x) * F(b) < 0 Then a = x Else b = x

Next i

MsgBox (a + b) / 2

End Sub

Sub ZolSech() ‘метод золотого сечения

n = 50

a = 0

b = 0.6

fi = (Sqr(5) + 1) / 2

For i = 1 To n

x = (b + fi * a) / (fi + 1)

If F(x) * F(b) < 0 Then a = x Else b = x

Next i

x = (b + fi * a) / (fi + 1)

MsgBox x

End Sub

Sub Iter() ‘Метод простой итерации

x = 0

e = 0.01

n = 5

For i = 1 To n

xn = x

x = x + F(x)

xn1 = x

Next i

If Abs(xn - xn1) < e Then res = xn

MsgBox res

End Sub

Sub Scan() ‘ Метод сканирования

h = 0.001

e = 0.001

x = 0

Do While x < 2.5

If Abs(F(x)) < e Then MsgBox x

x = x + h

Loop

End Sub

Sub MonteCarlo() ‘Метод Монте-Карло

n = 10000

e = 0.001

a = 0

b = 2.5

For j = 1 To 4 ‘ «запуски программы»

For i = 1 To n

x = a + Rnd * (b - a)

If Abs(F(x)) < e Then res = x

Next i

MsgBox res

Next j

End Sub

Задачи для самостоятельного решения

1. Решить уравнения численными методами

1. Уточнить корни нелинейных уравнений численными методами

3. Ускорение свободного падения при удалении от земной поверхности описывается следующей формулой , где h- высота над поверхностью Земли, R- ее радиус. При опускании тела вглубь Земли характер зависимости g от расстояния в приближении однородного шара меняется . Определить h, при условии .