Численные методы

1.1. Метод деления отрезка пополам.

Допустим, что мы нашли отрезок , в котором расположено искомое значение корня , т.е. .

Пусть для  определенности , (рис. 1.1). В качестве начального приближения корня принимается середина этого отрезка, т.е. . Далее исследуем значение функции на концах отрезков и . Тот из них, на концах которого принимает значения разных знаков, содержит искомый корень. Поэтому его принимаем в качестве нового отрезка. Вторую половину отрезка отбрасываем. В качестве первой итерации корня принимаем середину нового отрезка и т. д.

Рис. 1.1 Метод деления отрезка  пополам.

Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается  вдвое, т.е. после  итераций он сокращается в раз. Если длина полученного отрезка становится меньше допустимой погрешности, т.е. , счет прекращается.

       Пример 1.1. Найти решение уравнения c точностью методом деления отрезка пополам.

 

 

 

Рис. 1.2. Графический метод уравнения

Решение.  Уравнение представим в виде. Корнем данного уравнения является -координата точки пересечения графиков функций и (рис.1.2). Искомый корень находится между точками   и . Функция на концах отрезка принимает значения разных знаков и .

 

Начальное приближение:,  , (a+b)/2=-0.5.

;   ;   .

1-е приближение: ,  , .

Погрешность  .

.

Корень находится в интервале

2-е приближение:.

Погрешность  .

  .

Корень находится в интервале

…

7-е приближение:.

          Погрешность  .

Приближенным  решением данного уравнения является

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

Исходные данные Результаты   A B C D E 1 a b e x f(x) 2 -1 0 0,01 -0.20703 -0.00074

Function F(x)

    F = x ^ 3 -3*x^2+9* x =2

End Function

 

Sub program1()

    a = Cells(2, 1)

    b = Cells(2, 2)

    e = Cells(2, 3)

    If F(a) * F(b) > 0 Then

       MsgBox "F(a) и F(b) одного знака"

       End

    End If

1   x = (a + b) / 2

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

    If (b - a) >= e Then GoTo 1

    Cells(2, 4) = x

    Cells(2, 5) = F(x)

End Sub

 

Пример 1.2.Найти решение уравнения c точностью методом деления отрезка пополам с помощью программы Excel.

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

1. Введем в ячейки  A2, A3, A4, … значения переменной .
2. Введем в ячейку B2 формулу =A2^3+A2–1.
3. Скопируем формулу и вставим в остальные ячейки столбца B.
4. Найдем соседние ячейки, в которых значения функции имеют разные знаки (рис. 1.4 а). Соответствующие значения переменной дают границы интервала, содержащего корень.
5. Для построения графика вызываем мастер диаграмм. Выбираем тип диаграммы «точечная» - точечная диаграмма со значениями, соединенными сглаживающими линиями.

Границы интервала, содержащего корень, соответствуют значениям шкалы, между которыми линия графика пересекает горизонтальную ось.

       Продолжаем решение на новом листе (рис. 1.5).

1. Ввести в ячейки A1 – G1 заголовки столбцов.
2. В ячейку A2 – значение левой границы интервала  
3. В ячейку B2 – значение правой границы интервала  
4. В ячейку C2 – формулу середины отрезка  =(A2+B2)/2
5. В ячейку D2 – формулу погрешности    =B2–A2
6. В ячейку E2 – формулу функции     =A2^3+A2-1
7. Скопировать формулу из E2 в ячейки F2 и G2. Строка 2  теперь содержит результаты начального приближения.
8. В ячейку A3 – формулу    =ЕСЛИ(E2*G2<0;A2;C2)
9. В ячейку B3 – формулу    =ЕСЛИ(E2*G2<0;C2;B2)
10. Выделить ячейки C2:G2 и скопировать формулы в соседние ячейки C3:G3 при помощи маркера заполнения (небольшой черный квадрат в правом нижнем углу выделенного блока). Строка 3  теперь содержит результаты первого приближения.
11. Выделить ячейки A3:G3 и скопировать формулы в соседние ячейки расположенных ниже строк A4:G4, A5:G5, и т.д. при помощи маркера заполнения. Каждая новая строка содержит результаты очередного приближения.
12. В столбце С найти значение корня, соответствующее заданной точности.

Приближенное  решение данного уравнения    содержится в ячейке С9 (погрешность   в ячейке D9).

 

	A	B	C	D	E	F	G
1	a	b	x	b-a	F(a)	F(b)	F(x)
2	-1	0	-0.5	1,0000	-11	2	-3.375
3	-0.5	0	-0.25	0,5000	-3.375	2	-0.45313
4	-0.25	0	-0.125	0,2500	-0.45313	2	0.826172
5	-0.25	-0.125	-0.1875	0,1250	-0.45313	0.82617	0.200439
6	-0.25	-0.1875	-0.21875	0,0625	-0.45313	0.20044	-0.12277
7	-0.21875	-0.1875	-0.21313	0,0313	-0.12277	0.20044	0.039715
8	-0.21875	-0.21313	-0.21094	0,0056	-0.12277	0.03972	-0.04131
9	-0.21103	-0.21313	-0.20703	0.0078	-0.04131	0.03971	-0.00074
1.2. Метод Ньютона (метод касательных). Суть метода состоит в  том, что  на -й итерации в точке строится касательная к кривой и ищется точка пересечения касательной с осью абсцисс (рис. 1.6). Если задан интервал изоляции корня , то за начальное приближение принимается тот конец отрезка, на котором .     (1.1) Уравнение касательной, проведенной  к кривой в точке с координатами и , имеет вид:                                                           (1.2)                                                                                                           Рис. 1.3. Метод касательных.            За следующее приближение корня примем абсциссу точки пересечения касательной с осью OX. Из (1.2) при , получим      (1.3) При этом необходимо, чтобы  . Аналогично могут быть найдены  и следующие приближения  как точки пересечения с осью абсцисс касательных,  проведенных  в точках , и т.д. Формула для -го приближения имеет вид:     (1.4) Для завершения итерационного  процесса можно использовать условия  или . Объем вычислений в методе Ньютона больше, чем в других методах, поскольку приходится находить значение не только функции  , но и ее производной. Однако скорость сходимости здесь значительно выше. Пример 1.2. Решить уравнение на отрезке методом Ньютона c точностью . Решение. Определим производные заданной функции . Проверим выполнение условия сходимости на концах заданного интервала: - не выполняется, - выполняется. За начальное приближение корня можно принять . Находим первое приближение:   Аналогично находится  второе приближение: . Третье приближение:           Четвертое приближение:

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

 

Ниже приведена программа решения данного уравнения методом Ньютона. В качестве исходных данных вводятся начальное приближение и точность вычисления.

 

	Исходные данные		Результаты
	A	B	C	D
1	x0	e	x	F(x)
2	-1	0,01	-0,207	6,9E-0,9

 

Function F(x)     F = x ^ 3 -3*x^2 + 9*x + 2 End Function Function F1(x)     F1 = 3 * x ^ 2 -6*x + 9 End Function Sub program2()     x = Cells(2, 1)     e = Cells(2, 2) 1   xk = x - F(x) / F1(x)     If Abs(xk - x) >= e Then x = xk: GoTo 1     Cells(2, 3) = xk     Cells(2, 4) = F(xk) End Sub

 

Пример 1.3. Решить уравнение на отрезке методом Ньютона c точностью с помощью программы Excel.

Порядок решения.

1. Ввести в ячейки A1:D1 заголовки столбцов.
2. В ячейку A2 – значение начального приближения  
3. В ячейку B3 – формулу функции     =A2^3+A2-1
4. В ячейку C3 – формулу производной функции  =3*A2^2+1
5. В ячейку A3 – формулу первого приближения  =A2-B3/C3
6. В ячейку D3 – погрешность     =ABS(A3-A2)
7. Выделить ячейки A3:D3 и скопировать формулы в соседние ячейки расположенных ниже строк A4:D4, A5:D5, и т.д. при помощи маркера заполнения. Каждая новая строка содержит результаты очередного приближения.
8. В столбце A найти значение корня, соответствующее заданной точности.

Приближенное  решение данного уравнения  содержится в ячейке A6 (погрешность в ячейке  D6)

	A	B	C	D
1	x	F(x)	F'(x)	погрешность
2	-1
3	-0,38889	-11	18	0,611111
4	-0,21815	-2,01252	11,78704	0,17074
5	-0,207	-0,11649	10,45166	0,011146
6	-0,20696	-0,00045	10,37057	4,36E-05
Решение уравнения методом Ньютона  с помощью программы Excel.

 

1.3. Метод простой итерации.

Для использования  этого метода исходное нелинейное уравнение  необходимо привести к виду .

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

  или   .   (1.5)

Если  известно начальное приближение  корня  , подставляя это значение в правую часть уравнения , получаем новое приближение .

Далее подставляя каждый раз новое значение корня в уравнение , получаем последовательность значений:

, ,..., ,  k = 1,2,...,n.

Итерационный  процесс прекращается, если результаты двух последовательных итераций близки, т.е. .

Геометрическая интерпретация  метода простой итерации. Построим графики функций и . Корнем уравнения является абсцисса пересечения кривой с прямой (рис. 1.9). Взяв в качестве начальной точки , строим ломаную линию. Абсциссы вершин этой ломаной представляют собой последовательные приближения корня . Из рисунка видно, что если на отрезке (рис. 1.4а), то последовательные приближения колеблются около корня. Если же производная (рис. 1.4б), то последовательные приближения сходятся монотонно.

 

а)	б)
1.4. Геометрическая интерпретация метода простой итерации. Пример 1.4. Решить уравнение на отрезке методом простой итерации c точностью . Решение. Из условия сходимости (1.5)  , при определяем . Подставляя каждый раз новое  значение корня в уравнение  , получаем последовательность значений:                 Погрешность:   Приближенным решением данного уравнения c точностью является. Ниже приведена программа решения данного уравнения методом простой итерации. В качестве исходных данных вводятся начальное приближение, точность вычисления и значение постоянной М.         Исходные данные Результаты   A B C D E 1 x0 e M x F(x) 2 -1 0,001 18 -0,20734 -0,00398 Function F(x)     F = x ^ 3 + x - 1 End Function Sub program3()     x = Cells(2, 1)     e = Cells(2, 2)     M = Cells(2, 3) 1   xk = x - F(x) / M     If Abs(xk - x) >= e Then x = xk: GoTo 1     Cells(2, 4) = xk     Cells(2, 5) = F(xk) End Sub   Пример 1.4. Решить уравнение на отрезке методом простой итерации c точностью с помощью программы Excel. Порядок решения. Ввести в ячейки A1:D1 заголовки столбцов. В ячейку A2 – значение начального приближения   В ячейку B3 – формулу функции     =A2^3+A2-1 В ячейку C2 – значение M      5 В ячейку A3 – формулу первого приближения  =A2-B3/$C$2 В ячейку D3 – погрешность     =ABS(A3-A2) Выделить ячейки A3:D3 и скопировать формулы в соседние ячейки расположенных ниже строк A4:D4, A5:D5, и т.д. при помощи маркера заполнения. Каждая новая строка содержит результаты очередного приближения. В столбце A найти значение корня, соответствующее заданной точности. Приближенное решение данного  уравнения  содержится в ячейке A10 (погрешность   в ячейке  D10).   A B C D 1 x f(x) M погрешность 2 -1   18   3 -0,38889 -11   0,611111 4 -0,27708 -2,01252   0,111807 5 -0,23567 -0,74534   0,041408 6 -0,21896 -0,30079   0,016711 7 -0,21202 -0,12501   0,006945 8 -0,2091 -0,05256   0,00292 9 -0,20787 -0,0222   0,001233 10 -0,20734 -0,0094   0,000522