Инструкция . Введите выражение F(x) , нажмите Далее. Полученное решение сохраняется в файле Word . Также создается шаблон решения в Excel . Ниже представлена видеоинструкция.
Рассмотрим более быстрый способ нахождения корня на интервале , в предположении, что f(a)f(b)<0.
f’’(x)>0 f’’(x)<0
f(b)f’’(b)>0 f(a)f’’(a)>0
Рис.1а Рис. 1б
Рассмотрим рис.1а. Проведем через точки А и В хорду. Уравнение хорды
.
В точке x=x 1 , y=0, в результате получим первое приближение корня
. (3.8)
Проверяем условия
(а) f(x 1)f(b)<0,
(б) f(x 1)f(a)<0.
Если выполняется условие (а), то в формуле (3.8) точку a заменяем на x 1 , получим
.
Продолжая этот процесс, получим для n-го приближения
. (3.9)
Здесь подвижен конец a, то есть f(x i)f(b)<0. Аналогичная ситуация на рис 2а.
Рассмотрим случай, когда неподвижен конец a .
f’’(x)<0 f’’(x)>0
f(b)f’’(b)<0 f(a)f’’(a)<0
Рис.2а Рис.2б
На рис 1б,2б выполняется f(x i)f(a)<0. Записав уравнение хорды, мы на первом шаге итерационного процесса получим x 1 (см. (3.8)). Здесь выполняется f(x 1)f(a)<0. Затем вводим b 1 =x 1 (в формуле (3.8) точку b заменяем на x 1), получим
.
Продолжая процесс, придем к формуле
. (3.10)
Останов процесса
|x n – x n-1 |<ε; ξ≈x n
Рис. 3
На рис.3 f’’(x) меняет знак, поэтому подвижными будут оба конца.
Прежде чем перейти к вопросу о сходимости итерационного процесса метода хорд введем понятие выпуклой функции.
Определение.
Непрерывная на функция называется выпуклой (вогнутой), если для любых двух точек x 1 ,x 2 , удовлетворяющих a≤x 1
f(αx 1 + (1-α)x 2) ≥ αf(x 1) + (1-α)f(x 2) - вогнутая
Для выпуклой функции f’’(x)≥0.
Для вогнутой функции f’’(x)≤0
Теорема 3. Если функция f(x) выпукла (вогнута) на отрезке , то на любом отрезке график функции f(x) лежит не выше (не ниже) хорды, проходящей через точки графика с абсциссами x 1 и x 2 .
Доказательство:
Рассмотрим выпуклую функцию. Уравнение хорды: проходящей через x 1 и x 2 имеет вид:
.
Рассмотрим точку c= αx 1 + (1-α)x 2 , где aÎ
С другой стороны, по определению выпуклой функции имеем f(αx 1 + (1-α)x 2) ≤ αf 1 + (1-α)f 2 ; поэтому f(c) ≤ g(c) ч.т.д.
Для вогнутой функции доказательство аналогично.
Доказательство сходимости итерационного процесса рассмотрим для случая выпуклой (вогнутой) функции.
Теорема 4.
Пусть задана непрерывная: дважды дифференцируемая функция f(x) на и пусть f(a)f(b)<0, а f’(x) и f’’(x) сохраняют свои знаки на (см. рис 1а,1б и рис 2а,2б). Тогда итерационный процесс метода хорд сходится к корню ξ с любой наперед заданной точностью ε.
Доказательство:
Рассмотрим для примера случай f(a)f’’(a)<0 (см рис 1а и 2а). Из формулы (9) следует, что x n > x n -1 так как (b-x n -1)>0, а f n -1 /(f b -f n -1)<0. Это справедливо для любого n, то есть получаем возрастающую последовательность чисел
a≤x 0
. (3.11)
Имеем
(3.12)
(то есть значение функции y(x) в точке x n на хорде совпадает с f(ξ)).
Так как , то из (3.12) следует
или
. (3.13)
Для рис. 1а , следовательно
или
значит что и т.д. (см. (3.11)).
Для рис 2а . Следовательно, из (3.12) получим
значит
так как ч.т.д.
Аналогичное доказательство для рис.1б и рис.2б. Таким образом, мы доказали, что последовательность чисел является сходящейся.
a≤x 0
Сходимость метода хорд линейная с коэффициентом .
, (3.14)
где m 1 =min|f’(x)|, M 1 =max|f’(x)|.
Это вытекает из следующих формул. Рассмотрим случай неподвижного конца b и f(b)>0.
Имеем из (3.9) . Отсюда
. Учитывая, что , мы можем записать или
.
Заменяя в знаменателе правой части (ξ-x n -1) на (b-x n -1) и учитывая, что (ξ-x n -1)< (b-x n -1), получим , что и требовалось доказать (см. неравенство (3.14)).
Доказательство сходимости для случая рис.3 (f’’(x) меняет знак; в общем случае как f’, так и f’’ могут менять знаки) более сложное и здесь не приводится.
В задачах определить количество действительных корней уравнения f(x) = 0, отделить эти корни и, применяя метод хорд и касательных, найти их приближенные значения с точностью до 0.001.
Метод итераций
Метод простых итераций для уравнения f (x ) = 0 заключается в следующем:
1) Исходное уравнение преобразуют к виду, удобному для итераций:
x = φ (х ). (2.2)
2) Выбирают начальное приближение х
0 и вычисляют последующие приближения по итерационной формуле
x k
= φ
(х k
-1), k
=1,2, ... (2.3)
Если существует предел итерационной последовательности, он является корнем уравнения f (x ) = 0, т. е. f (ξ ) =0.
y = φ (х )
a x 0 x 1 x 2 ξ b
Рис. 2. Сходящийся процесс итераций
На рис. 2 показан процесс получения очередного приближения по методу итераций. Последовательность приближений сходится к корню ξ .
Теоретические основы для применения метода итераций дает следующая теорема.
Теорема 2.3 . Пусть выполняются условия:
1) корень уравнения х = φ(х) принадлежит отрезку [а , b ];
2) все значения функции φ (х ) принадлежат отрезку [а , b ],т. е. а ≤ φ (х )≤ b ;
3) существует такое положительное число q < 1, что производная φ "(x ) во всех точках отрезка [а , b ] удовлетворяет неравенству |φ "(x ) | ≤ q .
1) итерационная последовательность х п = φ (х п- 1)(п = 1, 2, 3, ...) сходится при любом x 0 Î [а , b ];
2) предел итерационной последовательности является корнем уравнения
х = φ (x ), т. е. если x k = ξ, то ξ= φ (ξ);
3) справедливо неравенство, характеризующее скорость сходимости итерационной последовательности
| ξ-x k | ≤ (b-a )×q k . (2.4)
Очевидно что, эта теорема ставит, довольно, жесткие условия, которые необходимо проверить перед применением метода итераций. Если производная функции φ (x ) по модулю больше единицы, то процесс итераций расходится (рис. 3).
y = φ (x ) y = x |
Рис. 3. Расходящийся процесс итераций
В качестве условия сходимости итерационных методов чисто используется неравенство
|x k - x k - 1 | ≤ ε . (2.5)
Метод хорд заключается в замене кривой у = f (x ) отрезком прямой, проходящей через точки (а , f (a )) и (b , f (b )) рис. 4). Абсцисса точки пересечения прямой с осью ОХ принимается за очередное приближение.
Чтобы получить расчетную формулу метода хорд, запишем уравнение прямой, проходящей через точки (a , f (a )) и (b , f (b )) и, приравнивая у к нулю, найдем х :
Þ
Алгоритм метода хорд :
1) пусть k = 0;
2) вычислим следующий номер итерации: k = k + 1.
Найдем очередное k -e приближение по формуле:
x k = a - f (a )(b - a )/(f (b ) - f (a )).
Вычислим f (x k );
3) если f (x k )= 0 (корень найден), то переходим к п. 5.
Если f (x k ) ×f (b )>0, то b = x k , иначе a = x k ;
4) если |x k – x k -1 | > ε , то переходим к п. 2;
5) выводим значение корня x k ;
Замечание . Действия третьего пункта аналогичны действиям метода половинного деления. Однако в методе хорд на каждом шаге может сдвигаться один и тот же конец отрезка (правый или левый), если график функции в окрестности корня выпуклый вверх (рис. 4, а ) или вогнутый вниз (рис. 4, б ).Поэтому в критерии сходимости используется разность соседних приближений.
Рис. 4. Метод хорд
4. Метод Ньютона (касательных )
Пусть найдено приближенное значение корня уравнения f (x )= 0, и обозначим его х п .Расчетная формула метода Ньютона для определения очередного приближения x n +1 может быть получена двумя способами.
Первый способ выражает геометрический смысл метода Ньютона и состоит в том, что вместо точки пересечения графика функции у = f (x )с осью Оx ищем точку пересечения с осью Оx касательной, проведенной к графику функции в точке (x n , f (x n )),как показано на рис. 5. уравнение касательной имеет вид у - f (x n )= f " (x n )(x - x n ).
Рис. 5. Метод Ньютона (касательных)
В точке пересечения касательной с осью Оx переменная у = 0. Приравнивая у к нулю, выразим х и получим формулу метода касательных :
(2.6)
Второй способ: разложим функцию f (x )в ряд Тейлора в окрестности точки х = х n :
Ограничимся линейными слагаемыми относительно (х - х п ),приравняем к нулю f (x ) и, выразив из полученного уравнения неизвестное х ,обозначив его через х n +1 получим формулу (2.6).
Приведем достаточные условия сходимости метода Ньютона.
Теорема 2.4 . Пусть на отрезке [а , b ]выполняются условия:
1) функция f (x )и ее производные f " (х )и f "" (x )непрерывны;
2) производные f " (x)и f ""(x )отличны от нуля и сохраняют определенные постоянные знаки;
3) f
(a
)× f
(b
) <
0 (функция f
(x
)меняет знак на отрезке).
Тогда существует отрезок [α
, β
], содержащий искомый корень уравнения f
(x
) =
0, на котором итерационная последовательность (2.6) сходится. Если в качестве нулевого приближения х
0 выбрать ту граничную точку [α
, β
], в которой знак функции совпадает со знаком второй производной,
т.е. f (x 0)× f" (x 0)>0, то итерационная последовательность сходится монотонно
Замечание . Отметим, что метод хорд как раз идет с противоположной стороны, и оба этих метода могут друг друга дополнять. Возможен и комбинированный метод хорд-касательных.
5. Метод секущих
Метод секущих может быть получен из метода Ньютона при замене производной приближенным выражением – разностной формулой:
, ,
. (2.7)
В формуле (2.7) используются два предыдущих приближения х п и x n - 1 .Поэтому при заданном начальном приближении х 0 необходимо вычислить следующее приближение x 1 , например, методом Ньютона с приближенной заменой производной по формуле
,
Алгоритм метода секущих :
1) заданы начальное значение х 0 и погрешность ε . Вычислим
;
2) для п = 1, 2, ... пока выполняется условие |x n – x n -1 | > ε , вычисляем х п+ 1 по формуле (2.7).
Численные методы 1
Решение нелинейных уравнений 1
Постановка задачи 1
Локализация корней 2
Уточнение корней 4
Методы уточнения корней 4
Метод половинного деления 4
Метод хорд 5
Метод Ньютона (метод касательных) 6
Численное интегрирование 7
Постановка задачи 7
Метод прямоугольников 8
Метод трапеций 9
Метод парабол (формула Симпсона) 10
На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Это происходит потому, что искомое решение обычно не выражается в элементарных или других известных функциях. Поэтому большое значение приобрели численные методы.
Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами. В зависимости от сложности задачи, заданной точности, применяемого метода может потребоваться огромное количество действий, и здесь без быстродействующего компьютера не обойтись.
Решение, полученное численным методом, обычно является приближенным, т. е. содержит некоторую погрешность. Источниками погрешности приближенного решения задачи являются:
погрешность метода решения;
погрешности округлений в действиях над числами.
Погрешность метода вызвана тем, что численным методом обычно решается другая, более простая задача, аппроксимирующая (приближающая) исходную задачу. В ряде случаев численный метод представляет собойбесконечный процесс , которыйв пределе приводит к искомому решению. Процесс, прерванный на некотором шаге, дает приближенное решение.
Погрешность округления зависит от количества арифметических действий, выполняемых в процессе решения задачи. Для решения одной и той же задачи могут применяться различные численные методы. Чувствительность к погрешностям округления существенно зависит от выбранного метода.
Решение нелинейных уравнений с одним неизвестным является одной из важных математических задач, возникающих в различных разделах физики, химии, биологии и других областях науки и техники.
В общем случае нелинейное уравнение с одним неизвестным можно записать:
f (x ) = 0 ,
где f (x ) – некоторая непрерывная функция аргументаx .
Всякое число x 0 , при которомf (x 0 ) ≡ 0, называется корнем уравненияf (x ) = 0.
Методы решения нелинейных уравнений делятся на прямые (аналитические, точные) иитерационные . Прямые методы позволяют записать решение в виде некоторого соотношения (формулы). При этом значения корней могут быть вычислены по этой формуле за конечное число арифметических операций. Подобные методы развиты для решения тригонометрических, логарифмических, показательных, а также простейших алгебраических уравнений.
Однако подавляющее большинство нелинейных уравнений, встречающихся на практике, не удается решить прямыми методами. Даже для алгебраического уравнения выше четвертой степени не удается получить аналитического решения в виде формулы с конечным числом арифметических действий. Во всех таких случаях приходится обращаться к численным методам, позволяющим получить приближенные значения корней с любой заданной точностью.
При численном подходе задача о решении нелинейных уравнений разбивается на два этапа: локализация (отделение) корней, т.е. нахождение таких отрезков на осиx , в пределах которых содержится один единственный корень, иуточнение корней , т.е. вычисление приближенных значений корней с заданной точностью.
Для отделения корней уравнения f (x ) = 0 необходимо иметь критерий, позволяющий убедится, что, во-первых, на рассматриваемом отрезке [a ,b ] имеется корень, а, во-вторых, что этот корень единственный на указанном отрезке.
Если функция f (x ) непрерывна на отрезке [a ,b ], а на концах отрезка её значения имеют разные знаки, т. е.
f (a ) f (b ) < 0 ,
то на этом отрезке расположен, по крайней мере, один корень.
Рис 1. Отделение корней. Функция f (x ) не монотонна на отрезке [a ,b ].
Это условие, как видно из рисунка (1), не обеспечивает единственности корня. Достаточным дополнительным условием, обеспечивающем единственность корня на отрезке [a ,b ] является требование монотонности функции на этом отрезке. В качестве признака монотонности функции можно воспользоваться условием постоянства знака первой производнойf ′(x ) .
Таким образом, если на отрезке [ a ,b ] функция непрерывна и монотонна, а ее значения на концах отрезка имеют разные знаки, то на рассматриваемом отрезке существует один и только один корень.
Воспользовавшись этим критерием, можно отделить корни аналитическим способом, находя интервалы монотонности функции.
Отделение корней можно выполнить графически , если удается построить график функцииy =f (x ) . Например, график функции на рисунке (1) показывает, что эта функция на интервале может быть разбита на три интервала монотонности и на этом интервале у нее существуют три корня.
Отделение корней можно также выполнить табличным способом. Допустим, что все интересующие нас корни уравнения (2.1) находятся на отрезке [A, B ]. Выбор этого отрезка (интервала поиска корней) может быть сделан, например, на основе анализа конкретной физической или иной задачи.
Рис. 2. Табличный способ локализации корней.
Будем вычислять значения f (x ) , начиная с точкиx =A , двигаясь вправо с некоторым шагомh (рис. 2). Как только обнаруживается пара соседних значенийf (x ) , имеющих разные знаки, так соответствующие значения аргументаx можно считать границами отрезка, содержащего корень.
Надежность табличного способа отделения корней уравнений зависит как от характера функции f (x ) , так и от выбранной величины шагаh . Действительно, если при достаточно малом значенииh (h <<|B −A |) на границах текущего отрезка [x, x +h ] функцияf (x ) принимает значения одного знака, то естественно ожидать, что уравнениеf (x ) = 0 корней на этом отрезке не имеет. Однако, это не всегда так: при несоблюдении условия монотонности функцииf (x ) на отрезке [x, x +h ] могут оказаться корни уравнения (рис. 3а).
Рис 3а Рис 3б
Также несколько корней на отрезке [x, x +h ] могут оказаться и при выполнении условияf (x ) f (x + h ) < 0 (рис. 3б). Предвидя подобные ситуации, следует выбирать достаточно малые значенияh .
Отделяя таким образом корни, мы, по сути, получаем их приближенные значения с точностью до выбранного шага. Так, например, если в качестве приближенного значения корня взять середину отрезка локализации, то абсолютная погрешность этого значения не будет превосходить половины шага поиска (h /2). Уменьшая шаг в окрестности каждого корня, можно, в принципе, повысить точность отделения корней до любого наперед заданного значения. Однако такой способ требует большого объема вычислений. Поэтому при проведении численных экспериментов с варьированием параметров задачи, когда приходится многократно осуществлять поиск корней, подобный метод не годится для уточнения корней и используется только для отделения (локализации) корней, т.е. определения начальных приближений к ним. Уточнение корней проводится с помощью других, более экономичных методов.
Наименование параметра | Значение |
Тема статьи: | Метод хорд. |
Рубрика (тематическая категория) | Математика |
Метод хорд - один из распространенных итерационных методов. Его еще называют методом линейного интерполирования, методом пропорциональных частей.
Идея метода хорд в том, что на достаточно малом отрезке дуга кривой у =f (x) заменяется хордой и абсцисса точки пересечения хорды с осью Ox является приближенным значением корня.
Рисунок 2 – Геометрическая интерпретация метода Ньютона.
Пусть для определенности f" (х)> 0, f"" (x) >0, f (а) <0, f (b)> 0 (рис. 3, а). Возьмем за начальное приближение искомого корня х* значения х 0 =а. Через точки а 0 и В проведем хорду и за первое приближение корня х* возьмем абсциссу x 1 точки пересечения хорды с осью ОХ. Теперь приближенное значение х 1 корня можно уточнить если применить метод хорд на отрезке [х 1 ; b ]. Абсцисса х 2 точки пересечения хордыА 1 В будет другим приближением корня. Продолжая данный процесс далее, получим последовательность х 0 , х 1 , х 2 ,..., х k , ... приближенных значений корня х* данного уравнения.
Таким образом метод хорд можно записать так:
, k=0, 1.2, …, (8)
В общем случае неподвижным будет тот конец отрезка изолированного корня, в которой знак функции f(х) совпадает со знаком второй производной, а за начальное приближение x 0 можно взять точку отрезка [а; b ], в которой f(x 0)×f"’(x 0) < 0.
К примеру, когда f (a) >0, f (b) <0, f"(х)< 0, f"(х)< 0 (рис. .3, б) конец b отрезка [а; b ] является неподвижным.
В случае если f (а)>0, f (b)< 0, f" (х)< 0, f"(x) >0 (рис.3, в), или f (а) <0, f (b) >0, f’ (х) >0, f"’ (x) <0 (рис. 3, г), точка а является неподвижным концом отрезка [а; b ].
Достаточные условия сходимости метода хорд дает такая теорема.
Рисунок 3. – Геометрическая интерпретация метода хорд
Теорема. Пусть на отрезке [а; b ] функция f (х) непрерывна вместе со своими производными второго порядка включительно, причем f(a)×f(b)<0, а производные f" (x) и f" (х) сохраняют свои знаки на [а; b ], тогда существует такая окружность корня х* уравнения f (x) =0, что для любого начального приближения х 0 этой окружности последовательность {х k }, вычисленная по формуле (8), сходится к корню х*.
Метод хорд. - понятие и виды. Классификация и особенности категории "Метод хорд." 2017, 2018.
Пусть 1) функция y=F(x) определена и непрерывна на отрезке . 2) F(a)F(b)<0 Требуется найти корень на отрезке с точностью &... .
При дифференцировании этим методом отмечают ряд точек на вычерченной кривой графика функции, которые соединяют хордами, т.е. заменяют заданную кривую ломаной линией (Рис.2). Принимают следующее допущение: угол наклона касательных в точках, расположенных посередине... .
В некоторых случаях несколько большей скоростью сходимости обладает метод хорд, у которого на втором этапе при выборе очередного приближения внутри отрезка, содержащего корень, учитывается величина невязки на концах отрезка: точка выбирается ближе к тому концу, где... .
Идея метода проиллюстрирована рисунком. Задается интервал , на котором f(x0)f(x1) &... .
В данном методе в качестве приближения выбирается не середина отрезка, а точка пересечения хорды с осью абсцисс. Уравнение хорды АВ, соединяющей концы отрезка: (1) Точка пересечения с осью абсцисс имеет координаты, подставим в (1) и найдем (2). Сравниваем знаки и... .
Если и - приближенные значения корня по недостатку и избытку. 1. Если на, то, при этом. 2. Если на, то, при этом. Пример. Отделить корни аналитически и уточнить их комбинированным методом хорд и касательных с точностью до 0,001. , следовательно, для вычислений...
Пусть на отрезке функция непрерывна, принимает на концах отрезка значение разных знаков, а производная f "(x) сохраняет знак. В зависимости от знака второй производной возможны следующие случаи расположения кривых (рис. 1).
Рис. 1.
Алгоритм приближенного вычисления корня методом хорд.
Исходные данные: f (x) - функция; е - требуемая точность; x 0 - начальное приближение.
Результат: xпр - приближенный корень уравнения f (x) = 0.
Метод решения:
Рис. 2. f "(x) f ""(x)>0 .
Рассмотрим случай, когда f "(x) и f ""(x) имеют одинаковые знаки (рис. 2).
График функции проходит через точки A 0 (a,f(a)) и B 0 (b,f(b)) . Искомый корень уравнения (точка x* ) нам неизвестен, вместо него возьмет точку х 1 пересечения хорды А 0 В 0 с осью абсцисс. Это и будет приближенное значение корня.
В аналитической геометрии выводится формула, задающая уравнение прямой, проходящей через две точки с координатами (х1; у1) и (х2; у2) : .
Тогда уравнение хорды А 0 В 0 запишется в виде: .
Найдем значение х = х 1 , для которого у = 0 : . Теперь корень находится на отрезке . Применим метод хорд к этому отрезку. Проведем хорду, соединяющую точки A 1 (x 1 ,f(x 1 )) и B 0 (b,f(b)) , и найдем х 2 - точку пересечения хорды А 1 В 0 с осью Ох : x 2 =x 1 .
Продолжая этот процесс, находим
x 3 =x 2 .
Получаем рекуррентную формулу вычисления приближений к корню
x n+1 =x n .
В этом случае конец b отрезка остается неподвижным, а конец a перемещается.
Таким образом, получаем расчетные формулы метода хорд:
x n+1 =x n ; x 0 =a . (4)
Вычисления очередных приближений к точному корню уравнения продолжается до тех пор, пока не достигнем заданной точности, т.е. должно выполняться условие: |x n+1 -x n |< , где - заданная точность.
Теперь рассмотрим случай, когда первая и вторая производные имеют разные знаки, т.е. f "(x) f ""(x)<0 . (рис. 3).
Рис. 3. Геометрическая интерпретация метода хорд для случая f "(x) f ""(x)<0 .
Соединим точки A 0 (a,f(a)) и B 0 (b,f(b)) хордой А 0 В 0 . Точку пересечения хорды с осью Ох будем считать первым приближение корня. В этом случае неподвижным концом отрезка будет являться конец а .
Уравнение хорды А 0 В 0 :. Отсюда найдем x 1 , полагая y = 0 : x 1 =b . Теперь корень уравнения x . Применяя метод хорд к этому отрезку, получим x 2 =x 1 . Продолжая и т.д., получим x n+1 =x n .
Расчетные формулы метода:
x n+1 =x n , x 0 =0 . (5)
Условие окончания вычислений: |x n+1 -x n |< . Тогда хпр = xn+1 с точностью Итак, если f "(x) f ""(x)>0 приближенное значение корня находят по формуле (4), если f "(x) f ""(x)<0 , то по формуле (5).
Практический выбор той или иной формулы осуществляется, пользуясь следующим правилом: неподвижным концом отрезка является тот, для которого знак функции совпадает со знаком второй производной.
Пример. Проиллюстрировать действие этого правила на уравнении
(x-1)ln(x)-1=0 , если отрезок изоляции корня .
Решение. Здесь f(x)=(x-1)ln(x)-1 .
f "(x)=ln(x)+;
f ""(x)= .
Вторая производная в этом примере положительна на отрезке изоляции корня : f ""(x)>0 , f(3) >0, т.е. f(b) f""(x)>0 . Таким образом, при решении данного уравнения методом хорд для уточнения корня выбираем формулы (4).
var e,c,a,b,y,ya,yb,yn,x,x1,x2,xn,f1,f2:real;
begin e:=0.0001;
writeln("vvedi nachalo otrezka");
writeln("vvedi konec otrezka");
y:=((x-1)*ln(x))-1;
y:=((x-1)*ln(x))-1;
yb:=y; c:=(a+b)/2; x:=c;
y:=((x-1)*ln(x))-1;
f1:=ln(x) + (x-1)/x ;
f2:= 1/x + 1/(x*x);
if (ya*yb < 0) and (f1*f2 > 0)
then begin x1:=a; while abs(x2 - x) > e do
x2:=x1 - (yn*(b-x1))/(yb - yn);
writeln("koren uravneniya xn = ", x2)
end elsebegin x1:=b;
while abs(x2 - x) > e do
begin x:=x1; y:=((x-1)*ln(x))-1; yn:=y;
x2:=x1 - (yn*(x1- a))/(yn - ya);
writeln("koren uravneniya xn = ", x2);
Метод простых итераций
Рассмотрим уравнение f(x)=0 (1) с отделенным корнем X . Для решения уравнения (1) методом простой итерации приведем его к равносильному виду: x=ц(x). (2)
Это всегда можно сделать, причем многими способами. Например:
x=g(x) · f(x) + x ? ц(x) , где g(x ) - произвольная непрерывная функция, не имеющая корней на отрезке .
Пусть x (0) - полученное каким-либо способом приближение к корню x (в простейшем случае x (0) =(a+b)/2). Метод простой итерации заключается в последовательном вычислении членов итерационной последовательности:
x (k+1) =ц(x (k) ), k=0, 1, 2, ... (3)
начиная с приближения x (0) .
УТВЕРЖДЕНИЕ: 1 Если последовательность {x (k) } метода простой итерации сходится и функция ц непрерывна, то предел последовательности является корнем уравнения x=ц(x)
ДОКАЗАТЕЛЬСТВО: Пусть. (4)
Перейдем к пределу в равенстве x (k+1) =ц(x (k) ) Получим с одной стороны по (4), что а с другой стороны в силу непрерывности функции ц и (4) .
В результате получаем x * =ц(x * ). Следовательно, x * - корень уравнения (2), т.е. X=x * .
Чтобы пользоваться этим утверждением нужна сходимость последовательности {x (k) }. Достаточное условие сходимости дает:
ТЕОРЕМА 1: (о сходимости) Пусть уравнение x=ц(x) имеет единственный корень на отрезке и выполнены условия:
ДОКАЗАТЕЛЬСТВО: Рассмотрим два соседних члена последовательности {x (k) }: x (k) = ц(x (k-1) ) и x (k+1) = ц(x (k) ) Tак как по условию 2) x (k) и x (k+1) лежат внутри отрезка , то используя теорему Лагранжа о средних значениях получаем:
x (k+1) - x (k) = ц(x (k) ) - ц(x (k-1) ) = ц "(c k )(x (k) - x (k-1) ), где c k (x (k-1) , x (k) ).
Отсюда получаем:
| x (k+1) - x (k) | = | ц "(c k ) | · | x (k) - x (k-1) | ? q | x (k) - x (k-1) | ?
? q (q | x (k-1) - x (k-2) |) = q 2 | x (k-1) - x (k-2) | ? ... ? q k | x (1) - x (0) |. (5)
Рассмотрим ряд
S ? = x (0) + (x (1) - x (0) ) + ... + (x (k+1) - x (k) ) + ... . (6)
Если мы докажем, что этот ряд сходится, то значит сходится и последовательность его частичных сумм
S k = x (0) + (x (1) - x (0) ) + ... + (x (k) - x (k-1) ).
Но нетрудно вычислить, что
S k = x (k)) . (7)
Следовательно, мы тем самым докажем и сходимость итерационной последовательности {x (k) }.
Для доказательства сходимости pяда (6) сравним его почленно (без первого слагаемого x (0) ) с рядом
q 0 | x (1) - x (0) | + q 1 |x (1) - x (0) | + ... + |x (1) - x (0) | + ..., (8)
который сходится как бесконечно убывающая геометрическая прогрессия (так как по условию q < 1 ). В силу неравенства (5) абсолютные величины ряда (6) не превосходят соответствующих членов сходящегося ряда (8) (то есть ряд (8) мажорирует ряд (6). Следовательно ряд (6) также сходится. Tем самым сходится последовательность {x (0) }.
Получим формулу, дающую способ оценки погрешности |X - x (k+1) |
метода простой итерации.
X - x (k+1) = X - S k+1 = S ? - S k+1 = (x (k+2) - (k+1) ) + (x (k+3) - x (k+2) ) + ... .
Следовательно
|X - x (k+1) | ? |x (k+2) - (k+1) | + |x (k+3) - x (k+2) | + ... ? q k+1 |x (1) - x (0) | + q k+2 |x (1) - x (0) | + ... = q k+1 |x (1) - x (0) | / (1-q).
В результате получаем формулу
|X - x (k+1) | ? q k+1 |x (1) - x (0) | / (1-q). (9)
Взяв за x (0) значение x (k) , за x (1) - значение x (k+1) (так как при выполнении условий теоремы такой выбор возможен) и учитывая, что при имеет место неравенство q k+1 ? q выводим:
|X - x (k+1) | ? q k+1 |x (k+1) - x (k) | / (1-q) ? q|x (k+1) - x (k) | / (1-q).
Итак, окончательно получаем:
|X - x (k+1) | ? q|x (k+1) - x (k) | / (1-q). (10)
Используем эту формулу для вывода критерия окончания итерационной последовательности. Пусть уравнение x=ц(x) решается методом простой итерации, причем ответ должен быть найден с точностью е, то есть
|X - x (k+1) | ? е.
С учетом (10) получаем, что точность е будет достигнута, если выполнено неравенство
|x (k+1) -x (k) | ? (1-q)/q. (11)
Таким образом, для нахождения корней уравнения x=ц(x) методом простой итерации с точностью нужно продолжать итерации до тех пор, пока модуль разности между последними соседними приближениями остается больше числа е(1-q)/q.
ЗАМЕЧАНИЕ 1: В качестве константы q обычно берут оценку сверху для величины
Геометрическая интерпретация
Рассмотрим график функции. Это означает, что решение уравнения и - это точка пересечения с прямой:
Рисунок 1.
И следующая итерация - это координата x пересечения горизонтальной прямой точки с прямой.
Рисунок 2.
Из рисунка наглядно видно требование сходимости. Чем ближе производная к 0, тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если, то каждое следующее приближение строится с другой стороны от корня:
Рисунок 3.
Заключение
Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов - сред и языков программирования.
Итогом работы можно считать созданную функциональную модель нахождения корней уравнения методами простой итерации, Ньютона, хорд и половинного деления. Данная модель применима к детерминированным задачам, т.е. погрешностью экспериментального вычисления которых можно пренебречь. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
Проведя исследования по теме курсовой работы "Численные методы. Решение нелинейных уравнений", я добилась поставленных во введении целей. Были подробно рассмотрены методы уточнения корней. К каждому определению и теореме были приведены несколько примеров. Все теоремы доказаны.
Использование различных источников дало возможность полностью раскрыть тему.