Приближенное вычисление корней в уравнениях
Приближенное вычисление корней в уравнениях
- Приближённое решение уравнений :
1.1 Способ хорд (или способ линейной интерполяции).
- Способ касательных (или способ Ньютона).
- Комбинированный способ (комбинированное применение способов хорд и касательных).
Приближённое решение уравнений.
Если квадратные уравнения решали уже древние греки, то способы решения алгебраических уравнений третьей и четвёртой степени были открыты лишь в XVI веке. Эти классические способы дают точные значения корней и выражают их через коэффициенты уравнения при помощи радикалов различных степеней. Однако эти способы приводят к громоздким вычислениям и поэтому имеют малую практическую ценность.
В отношении алгебраических уравнений пятой и высших степеней доказано, что в общем случае их решения не выражаются через коэффициенты при помощи радикалов. Не выражаются в радикалах, например, корни уже такого простого по виду уравнения, как:
Сказанное, однако, не означает отсутствия в науке методов решения уравнения высших степеней. Имеется много способов приближенного решения уравнений — алгебраических и неалгебраических (или, как их называют, трансцендентных), позволяющих вычислять их корни с любой, заранее заданной степенью точности, что для практических целей вполне достаточно.
На простейших из таких способов мы и остановимся, причём речь будет идти о вычислении действительных корней.
Пусть нужно решить уравнение:
Если обратиться к рисунку, то каждый корень уравнения (1) представляет собой абсциссу точки пересечения графика функции y=f(х)
C осью Ох (рисунок №1)
С помощью графика функции или каким-нибудь иным способом обычно удаётся установить приблизительные значения корней. Это позволяет для каждого корня получить грубые приближения по недостатку и по избытку. Такого рода грубых приближений во многих случаях оказывается достаточно, чтобы, отправляясь от них, получить все значения корня с требуемой точностью. Об этом и пойдёт речь.
Итак, пусть корень Е уравнения (1) «зажат» между двумя его приближениями а и b по недостатку и по избытку а
Способ хорд (или способ линейной интерполяции).
Проведём хорду АВ (рисунок№3) и за первое приближённое значение корня примем абсциссу x1 точки С пересечения хорды с осью Ох.
Уравнение хорды имеет вид:
Поэтому в точке С:
Рассмотрение всех четырёх случаев, изображённых на рисунке №2, показывает, что точка x1 лежит между a и b с той стороны от Е, где f(х) имеет знак, противоположный знаку f«(х).
Остановим внимание на первом случае: f`(х)>0, f«(х)>0 (рисунок №3), — в остальных случаях рассуждение вполне аналогично. В этом первом случае x1 лежит между a и Е. С отрезком [x1, b] поступаем так же, как мы поступаем с отрезком [a, b] (рисунок №4). При этом для нового приближённого значения корня получаем:
x1 = x2-(b- x1)*f(x1)/f(b)-f(x1)
( в формуле (2) заменяем x1 на x2, а на x1 ); значение x2 оказывается между x1 и Е. Рассматриваем отрезок [x2, b] и находим новое приближённое x3, заключённое между x2 и Е и. т. д. В результате получим последовательность а 0
Найдём первое приближённое значение корня по формуле (2):
так как f(1,588)=-0,817 0
Следовательно, искомый корень с точностью до 0,01 равен 1,64.
1.2 Способ касательных (или способ Ньютона).
В том из концов дуги АВ (рисунок №5), в котором знаки f(х) и f«(х) совпадают, проводим касательную и за первое приближённое значение корня принимаем абсциссу х1` точки Д пересечения этой касательной с осью Ох. Обратимся вновь к первому случаю, соответствующему первому рисунку №2 (f`(x)>0, f«(x)>0), — в остальных случаях рассуждают опять-таки аналогично. Уравнение интересующей нас касательной имеет вид:
и поэтому в точке Д:
Из рисунка видно, что x1` лежит между Е и b. С отрезком [a, x1`] поступаем так же, как с отрезком [a, b] ( рисунок №5), и в результате для нового приближённого значения корня получим:
х2` = x1`- f( x1`)/ f`( x1`).
Значение х2` оказывается между Е и x1`. Рассматриваем отрезок [a, х2`] и находим новое приближение х3` и т. д. В результате получим последовательность:
все более точных приближённых значений корня, причём:
xn+1`= xn`- f(xn`)/ f`( xn`) (8)
Эта формула справедлива для всех четырёх случаев, изображённых на рисунке 32. Для оценки погрешностей полученных приближений можно опять воспользоваться формулой (5), как и в первом случае, легко устанавливается сходимость последовальности x1`, х2`, х3`,…,xn`,… к значению Е
Пример №2. Методом касательных найдём положительный корень уравнения
с точностью до 0,01.
В этом уравнении f(х)=х^4-2x-4, f`(х)=4х^3-2,а f«(х)=12x^2.Так как f(х) и f«(х) при х0 = 1,7 имеют один и тот же знак, а именно:
f(1,7)=0,952>0 и f«(1,7)>0, то применяем формулу:
x1`= х0- f(х0)/ f`( х0), где f`(1,7)=4*1,7^3-2=17,652. Тогда
Применяем второй раз способ касательных:
х2= x1- f(x1)/ f` (x1), где f(x1)= f(1,646)=0,048, f` (1,646) =15,838;
f(1,643)=0,004, f` (1,643)=15,740;
Следовательно, искомый корень с точностью до 0,01 равен 1,64.
1.3 Комбинированный способ
(комбинированное применение способов хорд и касательных).
Этот способ состоит в одновременном использовании способов хорд и касательных. Остановим своё внимание опять на случае, отвечающем первому рисунку №2. Значения x1 и x1`, вычисляем по прежним формулам, т. е. принимаем:
x1`=b-f(b)/f`(b), причём: x1 0 изображён на рисунке №7. Из этого рисунка видно, что уравнение имеет положительный единственный корень, лежащий на отрезке 1 0,f«(x)>0 т. е. знак производных сохраняется. Применяем комбинированный способ:
Формулы (10) дают:
При этом x1`- x1=0,012, т. е. точность недостаточна. Совершаем второй шаг:
При этом х2`- х2=0,00018, т. е. точность достаточна. Таким образом:
Ошибка в тексте? Выдели её мышкой и нажми 
Остались рефераты, курсовые, презентации? Поделись с нами — загрузи их здесь!
Приближённые методы решения алгебраического уравнения
Реферат по курсу численных методов выполнил студент группы РЭ–01-1
Днепропетровский Национальный Университет
К афедра физики СВЧ
1. Численное решение уравнений с одним неизвестным
В данной работе рассматриваются метода приближённого вычисления действительных корней алгебраического или трансцендентного уравнения
на заданном отрезке [a, b].
Уравнение называется алгебраическим, если заданная функция есть полином n-ой степени:
f(x) = P(x) = a 0 x n + a 1 x n- 1 + … + a n -1 x + a n = 0, a 0 ¹ 0
Требование a 0 ¹ 0 обязательно, так как при невыполнении этого условия данное уравнение будет на порядок ниже.
Всякое уравнение (1.1) называется трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно лишь приближённо.
Однако в число алгебраических уравнений можно также включить те уравнения, которое после некоторых преобразований, можно привести к алгебраическому.
Те методы, которые здесь рассматриваются, применимы, как к алгебраическим уравнениям, так и к трансцендентным.
Корнем уравнения (1.1) называется такое число x, где f(x)=0.
При определении приближённых корней уравнения (1.1) необходимо решить две задачи:
отделение корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён один и только один корень уравнения (простой и кратный);
уточнение корней с заданной точностью (верным числом знаков до или после запятой);
Первую задачу можно решить, разбив данный промежуток на достаточно большое количество промежутков, где бы уравнение имело ровно один корень: на концах промежутков имело значения разных знаков. Там где данное условие не выполняется, те промежутки откинуть.
Вторая задача решается непосредственно в методах рассмотренных ниже.
При графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду:
и построить графики функций y 1 =j 1 (x), y 2 =j 2 (x).
Действительно, корнями уравнения (1.1)
f(x) = j 1 (x) — j 2 (x) = 0
являются абсциссы точек пересечения этих графиков (и только они).
Из всех способов, какими можно уравнение (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает наиболее простое построение графиков y 1 =j 1 (x) и y 2 =j 2 (x). В частности можно взять j 2 (x) = 0 и тогда придём к построению графика функции (1.1), точки пересечения которого с прямой y 2 =j 2 (x)=0, т. е. с осью абсцисс, и есть искомые корни уравнения (1.0).
Условия, наложенные на функцию f(x) на отрезке [a, b].
Будем предполагать, что функция f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на интервале) и имеет на этом интервале первую и вторую производные, причём обе они знакопостоянны (в частности отличны от нуля). Будем также предполагать, что функция f(x) принимает на концах отрезка значения разного знака. В силу знакопостоянства первой производной функция f(x) строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на интервале (a, b).
2. Метод дихотомии
Этот метод ещё называется методом вилки.
Нам необходимо найти корень уравнения (1.1) на отрезке [a, b]. Рассмотрим отрезок [x 0 , x 1 ]: [x 0 , x 1 ]Ì[a, b]. Пусть мы нашли такие точки х 0 , х 1 , что f (х 0 ) f(х 1 ) £ 0, т. е. на отрезке [х 0 , х 1 ] лежит не менее одного корня уравнения. Найдём середину отрезка х 2 =(х 0 +х 1 )/2 и вычислим f(х 2 ). Из двух половин отрезка выберем ту, для которой выполняется условие
f (х 2 ) f(х гран .) £ 0, так как один из корней лежит на этой половине. Затем новый отрезок делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис 1.2).
 принимает на левом конце отрезка [a, b] отрицательное значение, а на правом – положительное:</p><p>Возьмём среднюю точку отрезка [a, b], h=(a+b)/2 и вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где функция обращается в нуль. Если f(h)¹ 0, тогда из отрезков [a, h] и [h, b] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [a 1 , b 1 ]. По построению: f(a 1 ) 1 )>0. Затем среднюю точку отрезка [a 1 , b 1 ] точку h 1 и проведём тот же алгоритм нахождения другого отрезка [a 2 , b 2 ] где бы по построению f(a 2 ) 2 )>0. Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(h n )=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f(x)=0 решён, поэтому рассмотрим второй случай.</p><p>Неограниченное продолжение процесса даёт последовательность отрезков [a, b], [a 1 , b 1 ], [a 2 , b 2 ],… Эти отрезки вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:</p><p>a n £ a n+ 1 n+ 1 £ b n (1.2)</p><p>Длины отрезков с возрастанием номера n стремятся к нулю:</p><p style=)
Рассмотрим левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую ограниченную последовательность  и теореме о переходе к пределу в неравенствах имеем:</p><p style=)
Теперь рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную последовательность , которая тоже имеет предел. Обозначим его через с 2 :  пределы с 1 и с 2 удовлетворяют неравенству с 1 £ с 2 . Итак, a n £ с 1 2 £ b n , и следовательно:</p><p>с 2 -с 1 £ b n — a n =(b-a)/2n.</p><p>Таким образом, разность с 2 -с 1 меньше любого наперёд заданного положительного числа. Это означает, что с 2 -с 1 =0, т. е.: с 1 =с 2 =с</p><p>Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности Используя непрерывность функции f(x), докажем, что она является корнем уравнения f(x)=0.</p><p>Мы знаем, что f(a n ) n )£0 (3.2)</p><p>Аналогично, учитывая, что f(b n )³0, получаем, что:</p><p>f(c)=lim f(b n ) ³0 (4.2)</p><p>Из (3.2) и (4.2) следует, что f(c)=0. т. е. с – корень уравнения.</p><p>Процесс построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f(x)=0. На n-ом шаге процесса получаем:</p><p>Это двойное неравенство показывает, что число a n определяет корень с недостатком, а число b n с избытком, с ошибкой не превышающей длину отрезка Dn=b n -a n =(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность e>0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log 2 [(b-a)/e]: N>log 2 [(b-a)/e].</p><p>3. Метод итераций</p><p>Этот метод называется ещё методом последовательных приближений.</p><p>Пусть нам необходимо найти корень уравнения (1.1) на некотором отрезке [a, b].</p><p>Предположим, что уравнение (1.0) можно переписать в виде:</p><p>Возьмём произвольное значение x 0 из области определения функции j(x) и будет строить последовательность чисел <x n >, определённых с помощью рекуррентной формулы:</p><p>x n +1 =j(x n ), n=0, 1, 2, … (2.3)</p><p>Последовательность <x n >называется итерационной последовательностью. При её изучении встают два вопроса:</p><p>Можно ли процесс вычисления чисел x n продолжать неограниченно, т. е. будут ли числа x n принадлежать отрезку [a, b] ?</p><p>Если итерационный процесс (2.3) бесконечен, то как ведут себя числа x n при n®¥</p><p>Исследование этих вопросов показывает, что при определённых ограничениях на функцию j(x) итерационная последовательность является бесконечной и сходится к корню уравнения (1.3).</p><p style=)
 (3.3)</p><p>Однако для того, чтобы провести это исследование нам нужно ввести новое понятие.</p><p>Говорят, что функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует такая постоянная a, что для любых x 1 , x 2 , принадлежащих отрезку [a, b] имеет место неравенство:</p><p>| f(x 1 ) — f(x 2 )| £ a|x 1 — x 2 | (4.3)</p><p>Величину a в этом случае называют постоянной Липшица.</p><p>Если функция f(x), удовлетворяет на отрезке [a, b] условию Липшица, то она непрерывна на нём. Действительно, пусть x 0 – произвольная точка отрезка. Рассмотрим приращение функции f(x) в этой точке:</p><p>Df=f(x 0 +Dx) – f(x 0 )</p><p>и оценим его с помощью неравенства (4.3)</p><p style=)
Таким образом, .</p><p>Условие Липшица имеет простой геометрический смысл. Возьмём не графике функции y=f(x) две произвольные точки M 1 и M 2 с координатами (x 1 , f(x 1 )) и (x 2 , f(x 2 )). Напишем уравнение прямой линии, проходящей через эти точки:</p><p>где k– тангенс угла наклона прямой у оси Оx и определяется формулой:</p><p style=)
 удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном выборе точек M 1 и M 2 имеем |k|£a. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведённых через всевозможные пары точек графика функции y=f(x).</p><p><TABLE><TR><TD><img decoding=)
 имеет на отрезке [a, b] ограниченную производную:</p><p>| f ¢(x)| £ m; тогда она удовлетворяет условию Липшица с постоянной a=m. Для доказательс- тва этого утверждения воспользуемся формулой конечных приращений Лагранжа:</p><p>f(x 2 ) – f(x 1 ) = f ¢(x)(x 2 -x 1 ) (5.3)</p><p>где x 1 , x 2 , — произвольные точки отрезка [a, b] x, — некоторая точка отрезка [x 1 , x 2 ]. Возьмём модуль обеих частей равенства (4.3) и заменим в правой части | f ‘(x)| на m. В результате по- лучим неравенство (4.3) с a=m. Рис.2.3 даёт геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа (5.3) каждой секущей графика функции y = f(x) мож- но поставить в соответствие параллельную её касательную. Поэтому наибольший тангенс угла наклона касательных, и его можно оценить той же константой m: |k| £ m.</p><p>Познакомившись с условием Липшица, перейдём к изучению итерационной последовательности, предполагая, что уравнение имеет корень x=c. Существование этого корня можно установить с помощью качественного предварительного исследования уравнения с применением теоремы о существовании корня непрерывной функции.</p><p>Теорема о существовании корня непрерывной функции</p><p>Если функция f(x) непрерывна на отрезке [a, b] и принимает на его концах значения разных знаков, то на этом отрезке существует, по крайней мере, один корень уравнения f(x).</p><p>Теорема о сходимости итерационной последовательности</p><p>Пусть с – корень уравнения (2.3) и пусть функция j(x) удовлетворяет на некотором отрезке [c-d, c+d] (d>0) условию Липшица с постоянной a 0 на отрезке [c-d, c+d] существует бесконечная итерационная последовательность <x n >и эта последовательность сходится к корню x=c, который является единственным решением уравнения (1.3) на отрезке [c-d, c+d].</p><p>Сформулированная теорема имеет очень простой смысл. Будем говорить, что функция j осуществляет отображение точки x на точку y=j(x). Тогда условие Липшица с постоянной a 1 и x 2 больше, чем расстояние между их изображениями y 1 =j(x 1 ) и y 2 =j(x 2 ).</p><p>Корень c является неподвижной точкой отображения j, он преобразуется сам в себя c=j(c). Поэтому каждый шаг в итерационном процессе, сжимая расстояния должен приближать члены последовательности <x n >к неподвижной точке c.</p><p>После таких соображений поясняющих смысл теоремы, перейдём к её доказательству. Возьмём произвольную точку x 0 на отрезке [c-d, c+d], она отстоит от точки c не больше чем на d: |c-x 0 | £ d.</p><p>Вычислим x 1 : x 1 =j(x 0 ), при этом x 1 -c =j(x 0 )-j(c). Разность j(x 0 )-j(c) можно оценить с помощью условия Липшица:</p><p>|x 1 -c| = |j(x 0 )-j(c)| £ |x 0 -c| £ ad. (6.3)</p><p>Неравенство (6.3) показывает, что x 1 принадлежит отрезку [c-d, c+d] и расположен ближе к точке c, чем x 0 .</p><p>Продолжим построение итерационной последовательности. Вычислим x 2 : x 2 =j(x 1 ), при этом:</p><p>|x 2 -c| = |j(x 1 )-j(c)| £ a|x 1 -c| £ a 2 |x 0 -c| £ a 2 d</p><p>Точка x 2 опять принадлежит отрезку [c-d, c+d] и расположена ближе к точке c, чем точка x 1 , т.е. мы приблизились к c.</p><p>По индукции легко доказать, что последующие итерации также существуют и удовлетворяют неравенствам.</p><p>|x n -c| £ a n |x 0 -c| £ a n d (7.3)</p><p>Отсюда следует, что:</p><p style=)
 является единственным решением уравнения на отрезке [c-d, c+d]. Действительно, допустим, что существует ещё один корень x=c 1 .</p><p style=)
Примем c 1 за нулевое приближение и будем строить итерационную последователь- ность (2.3). Тогда с учётом (7.3) получим x n =c 1 (n=0, 1, 2, …). С другой стороны, по доказанному  может быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций.</p><p>4. Быстрота сходимости процесса итераций</p><p>Используем теперь производную функции j(x) для оценки скорости сходимости итераций при решении уравнения х=j(x). Нужно оценить скорость, с которой убывают погрешности a n =x-x n приближённых значений х 1 , … , х n , … корня x.</p><p style=)
 и х n+ 1 =j(х n ). Из них вытекает, что:</p><p>a n+ 1 = x-х n+ 1 =j(x)-j(х n )</p><p>Но по формуле Лагранжа имеем:</p><p>j(x)-j(х n )= j ¢(c n )·( x-x n )= j ¢(c n ) ·a n</p><p>где c n — точка лежащая между точками x и х n . Поэтому:</p><p>a n+ 1 =j ¢(c n ) ·a n (1.4)</p><p>Из равенства (1.4) вытекает следующий вывод:</p><p>Пусть x – корень уравнения x=j (x) — лежит на отрезке [a, b]. Если на этом отрезке выполняется неравенство |j ¢(x)| 1 также выбрано на отрезке [a, b], то при любом n выполняется соотношение:</p><p>|a n+ 1 | n ·|a 1 | (2.4)</p><p>В самом деле, из равенства (1.4) имеем:</p><p>Но точка c 1 лежит на отрезке [a, b] (рис.1.4), и потому:</p><p>Точно так же получаем, что:</p><p>|a 3 |=|j ¢(c 1 )|·|a 2 | 2 | 2 ·|a 1 |</p><p>Тем самым наше утверждение доказано.</p><p>Так само при 0 2 , q 3 , … , q n , … стремится к нулю, то и погрешность a n+ 1 стремится к нулю с возрастанием n. Иными словами, при указанных выше предположениях числа x 1 , x 2 , … , x n , … приближаются к числу x, причём разность |x-x n | убывает быстрее, чем q n ·|a 1 |.</p><p>Точно так же можно доказать, что если на отрезке [a, b] выполнено неравенство:</p><p>то процесс итераций расходится.</p><p>Особенно быстро сходится процесс последовательных приближений, если в точке x производная функции j(x) обращается в нуль. В этом случае по мере приближения к x, значение j ¢(x) стремится к нулю. Так как:</p><p>|a n+ 1 |=|j ¢(c n )|·|a n |</p><p>то сходимость процесса ускоряется по мере приближения к точке x.</p><p style=)
Однако то же самое можно наблюдать в методе Ньютона, при замене f(x)=0 на =0 — в методе Ньютона наблюдается ускорение сходимости процесса приближений.</p><p>5. Метод касательных (метод Ньютона)</p><p>Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x 0 и запишем в ней уравнение касательной к графику функции f(x):</p><p>y=f(x 0 )+ f ¢(x) (x-x 0 ) (1.5)</p><p>Графики функции f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x 1 пересечения касательной с осью Ox будет расположена недалеко от корня c (рис. 1.5)</p><p>Для определения точки имеем уравнение:</p><p>f(x 0 )+ f ¢(x 0 ) (x 1 -x 0 )=0</p><p>таким образом: x 1 =x 0 – f (x 0 )/ f ¢(x 0 ) (2.5)</p><p>Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x 1 и найдём для неё точку пересечения x 2 с осью Ox (см. рис.1.5) x 2 =x 1 – f (x 1 )/ f ¢(x 1 ). Продолжая этот процесс, получим последовательность <x n >, определён- ную с помощью рекуррентной формулы:</p><p>x n + 1 =x n – f (x n )/ f ¢(x n ), n=0, 1, 2, … (3.5)</p><p style=)
 бесконечен, то как ведёт себя последовательность <x n >при n®¥ ?</p><p>При анализе этих вопросов предположим, что корень x=c является внутренней точкой отрезка [a, b] (a 0, | f ¢¢(x)|£M, xÎ[a, b], (4.5)</p><p>и докажем следующую теорему.</p><p>Теорема о сходимости метода касательных.</p><p style=)
Если функция f(x) удовлетворяет условиям, сформулированным п.1., то найдётся такое d: 0 :</p><p style=)
 и равенством её нулю в точке x= с:</p><p style=)
</p><p style=)
Тогда в силу (8.5) для данного e можно указать такое d: 0 
 удовлетворяет на отрезке [c-d, c+d] Ì [a, b] условию Липшица с постоянной a=0.5 0 на отрезке [c-d, c+d] существует бесконечная последовательность <x n >, x n +1 =j(x n ), n=0, 1, 2, …, сходящаяся к корню x=c.</p><p>Теперь нам остаётся заметить, что итерационной последовательностью для уравнения (5.5), сходимость которой мы только что установили, является последовательность (3.5) метода касательных. Теорема доказана.</p><p>Требование близости нулевого приближения x 0 к искомому корню c является существенным для метода касательных. На рис.2.5 изображён график, где х 0 выбрано неправильно, то есть расстояние сх 0 >ас, так как ас 1 не принадлежит отрезку [a, b], и на этом процесс построения рекуррентной последовательности метода касательных обрывается.</p><p>Таким образом, до начала расчётов по данному методу для выбора нулевого приближения х 0 нужно знать область локализации искомого корня х=с. Если известен в общих чертах график функции f(x), то его легко определить по этому графику. В случае необходимости можно сделать несколько шагов по методу вилки. Затруднения, связанные с предварительным исследованием уравнения, вполне окупаются высокой скоростью сходимости метода.</p><p style=)
 на отрезке [a, b] непрерывна и дважды дифференцируема, и имеет ровно один корень, тогда можно взять за нулевое приближение значение одного из концов отрезка [a, b] в зависимости от знака второй производной, иначе при первом же приближении можно попасть за пределы отрезка [a, b] (рис. 1.6).</p><p style=)
 имеет различные знаки, причём на отрезке [a, b] вторая производная положительна. Тогда за начальное приближение х 1 надо выбирать ту из точек a или b, в которой функция f(x) принимает положительное значение. Если же на отрезке [a, b] вторая производная отрицательна, то за начальное приближение x 1 надо выбирать ту точку, в которой функция f(x) принимает отрицательное значение.</p><p>7. Метод секущих</p><p style=)
. Такие процессы, где для вычисления очередного приближения надо знать два предыдущих, называют двух шаговыми.</p><p style=)
Эти изменения сильно меняют характер итераций. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и малой окрестности корня. Скорость сходимости также изменяется. Его можно оценить, разлагая все функции в (1.7) по формуле Тейлора с центром 
, получим:</p><p>ab=1, b 2 — b — 1 = 0 (3.7)</p><p>Только положительный корень b квадратного уравнения (3.6) соответствует убыванию ошибки, т. е. сходящемуся процессу. Следовательно, в методе секущих</p><p style=)
. Но в методе на каждой итерации надо вычислять и функцию, и производную, а в методе секущих – только функцию. Поэтому при одинаковом объёме вычисления в методе секущих можно сделать вдвое больше итераций и получить более высокую точность. Что является более приемлемым при численных расчётах на ЭВМ, чем метод касательных.</p><p>В знаменателе формулы (1.7) стоит разность значений функции. Вдали от корня это несущественно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение невелико. Приводить к общему знаменателю уравнение (1.7) не следует: может увеличится потеря точности в расчётах.</p><p>От «разболтки» страхуются так называемым приёмом Гарвика. Выбирают не очень малое e, ведут итерации до выполнения |x n + 1 -x n | n + 1 -x n | убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют.</p><p>8. Метод хорд, или линейной аппроксимации</p><p>Рассмотрим задачу решения уравнения (1.1) методом хорд.</p><p>Этот метод состоит в следующем. График функции f(x) заменяется её хордой, т. е. отрезком соединяющий концевые точки графика функции f(x): точки (a, f(a)) и (b, f(b)). Абсцисса х 1 точки пересечения этой хорды с осью Ох и рассматривается, как первое приближение искомого корня (рис 1.8). Далее берётся тот из отрезков [a, x 1 ] и [x 1 , b], на концах которого, функция f(x) принимает значения разного знака (далее будет показано, что при сделанных предположениях f(x) ¹ 0 и, следовательно, такой отрезок всегда существует), и к нему применяется тот же приём; получается второе приближение корня х 2 и т. д. В результате образуется последовательность х n , n=1, 2, … которая, как это будет показано, при сделанных ограничениях на функцию f(x), сходится к корню уравнения f(x).</p><p>Легко получить рекуррентные формулы для указанных чисел х n , n=1, 2,… Уравнение прямой, проходящее через крайние точки графика функции f(x) имеет вид:</p><p style=)
, т. е. Запишем уравнение в виде:</p><p>Найдём абсциссу х 1 точки пересечения прямой (1.8) с осью Ох, т. е. Решим уравнение l(x)=0; получим:</p><p style=)
a 1 </p><p>Покажем, что последовательность <x n >стремится к корню уравнения (1.0) монотонно.</p><p>Предположим для определённости, что f ¢(x) и f ¢¢(x) >0, a f(x), a > x > b</p><p>В частности, если х 0 корень уравнения (1.1): f(x 0 ) = 0, отсюда следует, что</p><p>C (3.8) и (4.8) получаем:</p><p>l(x) = 0, a > x 1 > b</p><p>но линейная функция l(x) строго монотонно возрастает, так как</p><p>поэтому из (5.8) следует x 1 0 , заменяя теперь отрезок [a, b] отрезком [x 1 , b] и замечая, что f(x 1 ) 1 2 0 , далее по индукции получим:</p><p>Таким образом, последовательность <x n >, будучи монотонной, сходится. Пусть lim x n = c, при n®¥ . Переходя к пределу при n®¥ в равенстве (4.8) получим f(c)=0, т. е. последовательность <x n >сходится к корню уравнения (1.1).</p><p>Если | f ¢(x)|³m>0, a n > через значения самой функции f(x) в точках x n . Действительно,</p><p>f(x n )= f(x n )- f(x 0 )= f ¢(x n )×(x n -x 0 ),</p><p>x n n 0 , n = 1, 2, …,</p><p style=)
.</p><p style=)
 б)</p><p>Формула, при которой мы используем два последних приближения, имеет вид:</p><p style=)
, f(b), f(a 1 ), если f(a) 0,</p><p style=)
>0</p><p>Если случайно окажется, что точка а 3 , вычисленная по формуле (1.9), лежит за пределами отрезка [a, b], то на следующем шаге надо вместо этой точки взять ближайший к ней конец этого отрезка (рис. 1.9, б). Оказывается, что сходимость усовершенствованного метода хорд гораздо быстрее, чем у обычного. Именно, если x — корень уравнения f(x)=0, то:</p><p style=)
|a n + 1 | n -x| S , где  обращён вогнутостью вверх, то находят точки а 1 и х 1 по формулам:</p><p style=)
 обращён вогнутостью вниз, то точку а 1 находят по формуле (1.10), а точку х 1 – по формуле:</p><p style=)
 и б), корень x уравнения f(x)=0 лежит обычно между полученными точками а 1 и х 1 . Применяя снова к этим точкам формулы метода хорд и метода Ньютона, получают новую пару точек а 2 и х 2 и т. д.</p><p>Таким путём получают две последовательности точек а 1 , а 2 , а 3 , …, a n , … и x 1 , x 2 , x 3 , … , x n , …, приближаются с разных сторон к искомому корню x. Преимущество описанного метода состоит в том, что при нём получаются приближённые значения как с избытком так и с достатком.</p><p style=)
: он только требует непрерывности функции. Остальные методы накладывают более сильные ограничения. Во многих случаях это преимущество метода вилки может оказаться существенным.</p><p>С точки зрения организации вычислительного процесса все виды численного нахождения корней уравнения очень просты. Однако и здесь метод деления пополам обладает некоторым преимуществом. Вычисления можно начинать с любого отрезка [a, b], на концах которого непрерывная функция f(x) принимает значения разных знаков. Процесс будет сходится к корню уравнения f(x)=0, причём на каждом шаге он даёт для корня двустороннюю оценку, по которой легко определить достигнутую точность. Сходимость же метода итераций или касательных зависит от того, насколько удачно выбрано нулевое приближение.</p><p>Наибольшей скоростью сходимости обладает метод касательных. В случае, когда подсчёт значений функции f(x) сложен и требует больших затрат машинного времени, это преимущество становится определяющим. На вопрос о том, какой метод – метод итераций или дихотомия даёт большую скорость сходимости, однозначно ответить нельзя. При методе дихотомии знаменатель геометрической прогрессии убывания погрешности равен q=0.5, а при методе хорд он может принимать значения 0 0 накладывались определённые ограничения. Однако при решении конкретных задач проверить их выполнение часто бывает трудно и даже практически не возможно. Функция может не задаваться в виде простой формулы, а находится в результате численного решения некоторой математической задачи, получаться из измерений и проверять «экспериментально»: начинают расчёт и следят за поведением первых членов последовательности <x n >. Если по ним видно, что процесс сходится, то расчёт продолжают, пока не достигнут нужной точности. В противном случае вычисления прекращают и анализируют полученные данные, пытаясь установить причину рассходимости и, в соответствии с ней выбрать другой метод решения задач.</p><p>А. Н. Тихонов, Д. П. Костомаров «Вводные лекции по прикладной математике»</p><p>Л. Д. Кудрявцев «Математический анализ т. 2» М. 1984 «Наука»</p><p>П. Ф. Фильчаков «Справочник по высшей математике» К. 1973 «Наукова Думка»</p><p>Н. Н. Калиткин «Численные методы» М. «Наука» 1978</p><p>Н. Я. Виленкин «Итерационные методы» М. «Наука» 1984</p><h2>Модуль 1. Модуль 1. Численные методы решения нелинейных уравнений. Нахождение арифметического корня натуральной степени с заданной точностью</h2><p style=)
Модуль 1. Модуль 1. Численные методы решения нелинейных уравнений. Нахождение арифметического корня натуральной степени с заданной точностью.
1. Численные методы решения нелинейных уравнений.
1.1. Постановка задачи.
1.2. Этапы приближенного решения нелинейных уравнений.
1.3. Уточнение корней методом деления отрезка пополам.
1.4. Уточнение корней методом касательных.
1.5. Уточнение корней методом хорд.
2. Нахождение арифметического корня натуральной степени с заданной точностью.
Литература.
1. Численные методы решения нелинейных уравнений.
1.1. Постановка задачи.
Пусть имеется уравнение вида
где f (x) — заданная алгебраическая или трансцендентная функция. (Функция называется алгебраической, если для получения её значения нужно выполнить арифметические операции и возведение в степень с рациональным показателем. Примеры трансцендентных функций — показательная, логарифмическая, тригонометрические, обратные тригонометрические.)
Решить уравнение — значит найти все его корни, то есть те значения x, которые обращают уравнение в тождество, или доказать, что корней нет.
Если алгебраическое или трансцендентное уравнение достаточно сложно, то довольно редко удается точно найти его корни. Кроме того, в некоторых случаях уравнение может содержать коэффициенты, известные лишь приблизительно, поэтому сама задача о точном нахождении корней теряет смысл. В таких случаях применяют численные (приближенные) методы решения.
Поставим задачу найти такое приближенное значение корня xпр, которое мало отличается от точного значения корня x*, так что выполняется неравенство │x* – xпр │ 0, m – натуральное.
Известен следующий рекуррентный (итерационный) процесс нахождения членов последовательности t0, t1, t2, …, где
, n = 0, 1, 2, … . (6)
При этом оказывается [4], что полученная последовательность сходится при любом t0>0 к точному значению 
и при том достаточно быстро.
Удобно в качестве t0 брать значение с одной верной значащей цифрой, которую легко найти подбором.
Итерационный процесс нахождения очередного приближения к величине корня прекращается, как только выполнится неравенство 
. При этом 
с точностью ε.
Пример 5. Найти 
с точностью ε = 0,000001 (или ε = 10-6).
Решение. Здесь a = 1,25, ε = 10-6. Пусть t0 = 1,1 (т. к. 1,12≈1,25). Из формулы (6) при m = 2 имеем:
, n = 0, 1, 2, … .
Значит 
. Так как требуется найти значение корня с точностью ε = 10-6, т. е. с шестью верными значащими цифрами после запятой, при вычислении t1 количество цифр после запятой берем с запасом (например, семь цифр).
Аналогично вычисляем t2 = 1,1180339…; 
. Продолжаем итерационный процесс: t3 = 1,1180339… . Итак, на третьем шаге (итерации) результат в требуемых знаках (шесть цифр после запятой) повторился, т. е. 
.
Значит, 
с точностью 10-6.
3. Практикум.
Численные методы решения нелинейных уравнений.
В заданиях данной группы нужно выбрать правильные ответы из приведенного списка. Обратите внимание, что правильный ответ может быть не единственным. Вам надо указать через запятую буквы соответствующие правильным высказываниям.
1. Какие из следующих функций являются трансцендентными?
2. Поиск корней методом половинного деления применим к функциям:
a) к многочленам любых степеней.
b) к непрерывным, но не дифференцируемым функциям.
c) к функциям, имеющим разрывы.
d) любым непрерывным.
3. Отметьте высказывания, относящиеся к поиску корней методом половинного деления:
a) Существуют уравнения, для которых есть только численное решение и нет аналитического.
b) Это самый быстрый метод поиска корней.
c) Это самый точный метод.
d) Это один из самых простых вычислительных методов поиска корней уравнения
e) Этот метод не требует дополнительных условий сходимости.
f) Этим методом можно искать корни многочленов любых степеней.
В заданиях данной группы нужно выбрать правильный ответ из приведенного списка. Обратите внимание, что правильный ответ должен быть единственным
4. Решить уравнение, значит
a) найти такие значения неизвестного, которые при подстановке в уравнение, обращают его в тождество;
b) доказать, что таких значений неизвестного, которые при подстановке в уравнение, обращают его в тождество нет;
c) найти такие значения неизвестного, которые при подстановке в уравнение, обращают его в тождество или доказать, что корней нет;
d) найти такие значения неизвестного, которые при подстановке в уравнение, обращают его в верное тождество и доказать, что корней нет.
5. Для какой из приведенных ниже функций y = f(x) уравнение f(x) = 0 не имеет корней
6. Отделение корней уравнения f(x)=0 – это
a) нахождение интервалов длиной ε из области определения функции y=f(x);
b) нахождение корней из области определения функции y=f(x);
c) нахождение интервалов с одним корнем вне области определения функции y=f(x);
d) нахождение интервалов из области определения, в каждом из которых содержится ровно один корень.
7. Какая из этих формул верна и применяется в методе деления отрезка пополам для определения достижения точности?
8. Какая из этих формул верна и применяется в методе деления отрезка пополам для определения X – приближённого значение корня на отрезке [a; b]?
9. Аналитическое отделение корней уравнения f(x) = 0 основано на теореме:
a) если функция f(x) непрерывна на [a, b], принимает на концах отрезка значения разных знаков, то на этом отрезке содержится хотя бы один корень;
b) если f ‘(x) существует и непрерывна, то на этом отрезке содержится хотя бы один корень;
c) если функция f(x) принимает на концах отрезка [a, b] значения разных знаков, то на этом отрезке содержится хотя бы один корень;
d) если f ‘(x) непрерывна и меняет знак на [а, b], то на этом отрезке содержится хотя бы один корень.
10. Необходимым условием сходимости метода касательных при решении уравнения у = f(x) является:
a) f(x) непрерывна на [a, b] и сохраняет на нем свой знак;
b) f ‘(x) существует и сохраняет знак;
c) f(x) и f ‘(x) непрерывны на [a, b] и сохраняют знак;
d) f(x) непрерывна и меняет знак на отрезке [a, b], f ‘(x) непрерывна и сохраняет знак на отрезке [a, b].
11. Укажите интервал изоляции корня уравнения 
.
12. Какому графику соответствуют условия 
, 
, 
, 
, 
?
13. Известно, что уравнение имеет три корня. Минимальное количество начальных точек, определяющих отрезки изоляции корней, для полного решения методом половинного деления:
В заданиях данной группы нужно вписать числовой ответ или дополнить предложение.
14. Дано нелинейное уравнение x2sinx + 1 = 0 и начальное приближение x0 = 3,3. Первое приближение x1 в методе Ньютона равно (ответ округлить до трех знаков после запятой) ____________.
15. Дано уравнение x2sinx + 1 = 0. Известно, что на отрезке [3,2; 3,5] существует единственный корень уравнения. После выполнения одного шага методом деления отрезка пополам, отрезок станет равен _____________________________.
http://www.km.ru/referats/2923FEFE93A540F6801A8AFA0BAE264A
http://pandia.ru/text/80/140/28639.php