Xreferat.com » Рефераты по математике » Приближённые методы решения алгебраического уравнения

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

x2, … , xn, … приближаются к числу x, причём разность |x-xn| убывает быстрее, чем qn·|a1|.

Точно так же можно доказать, что если на отрезке [a, b] выполнено неравенство:

|j ¢(x)|>1,

то процесс итераций расходится.

Особенно быстро сходится процесс последовательных приближений, если в точке x производная функции j(x) обращается в нуль. В этом случае по мере приближения к x, значение j ¢(x) стремится к нулю. Так как:

|an+ 1|=|j ¢(cn)|·|an|

то сходимость процесса ускоряется по мере приближения к точке x.

Однако то же самое можно наблюдать в методе Ньютона, при замене f(x)=0 на Приближённые методы решения алгебраического уравнения имеем:Приближённые методы решения алгебраического уравнения и её производная:Приближённые методы решения алгебраического уравнения в точке x: f(x)=0 - в методе Ньютона наблюдается ускорение сходимости процесса приближений.

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

Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x0 и запишем в ней уравнение касательной к графику функции f(x):

y=f(x0)+ f ¢(x) (x-x0) (1.5)

Графики функции f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с осью Ox будет расположена недалеко от корня c (рис. 1.5)

Для определения точки имеем уравнение:

f(x0)+ f ¢(x0) (x1-x0)=0

таким образом: x1=x0 – f (x0)/ f ¢(x0) (2.5)

Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x1 и найдём для неё точку пересечения x2 с осью Ox (см. рис.1.5) x2=x1 – f (x1)/ f ¢(x1). Продолжая этот процесс, получим последовательность {xn}, определён- ную с помощью рекуррентной формулы: 

xn+ 1=xn – f (xn)/ f ¢(xn), n=0, 1, 2, … (3.5)

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

рис. 1.5 

Построение последовательности  {xn}по методу касательных   

При исследовании этой последовательности, как и последовательности метода итераций, встают два вопроса:

Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?

Если процесс (3.5) бесконечен, то как ведёт себя последовательность {xn} при n®¥ ? 

При анализе этих вопросов предположим, что корень x=c является внутренней точкой отрезка [a, b] (a<c<b), а функция f(x) дважды дифференцируема на данном отрезке, причём её производные удовлетворяют неравенствам:

| f ¢(x)|³m>0, | f ¢¢(x)|£M, xÎ[a, b], (4.5)

и докажем следующую теорему.

Теорема о сходимости метода касательных.

Если функция f(x) удовлетворяет условиям, сформулированным п.1., то найдётся такое d: 0<d£min(c–a, b–c), что при любом выборе начального приближения на отрезке [c-d, c+d] Ì [a, b] существует бесконечная итерационная последовательность (3.5) и эта последовательность сходится к корню c.

Доказательство. В силу предположения о дифференцируемости функции f(x) и не равенстве нулю её производной f ¢(x) уравнение f(x)=0 эквивалентно на отрезке [a, b] уравне- нию: 

x=j(x), j(x)=x– f (x)/ f ¢(x) (5.5)

так что корень x=c исходного уравнения является одновременно корнем уравнения (5.4). 

Исследуем возможность отыскания этого корня с помощью итераций.

Вычислим производную функции j(x):

Приближённые методы решения алгебраического уравнения (6.5)

и оценим полученное выражение. Согласно неравенствам (4.5):

Приближённые методы решения алгебраического уравнения (7.5)

Для дальнейшей оценки |Приближённые методы решения алгебраического уравнения| воспользуемся непрерывностью функции f(x) и равенством её нулю в точке x= с:

Приближённые методы решения алгебраического уравнения (8.5)

Положим e=m2/(2M)

Тогда в силу (8.5) для данного e можно указать такое d: 0<d£ min (c–a, b–c), что для всех Приближённые методы решения алгебраического уравнения выполняется неравенство:

Приближённые методы решения алгебраического уравнения (9.5)

Учитывая это, получим:

Приближённые методы решения алгебраического уравнения (10.5)

Таким образом, функция j(x) удовлетворяет на отрезке [c-d, c+d] Ì [a, b] условию Липшица с постоянной a=0.5<1. Это означает, что уравнение (5.5) можно решать методом итераций: при любом выборе нулевого приближения x0 на отрезке [c-d, c+d] существует бесконечная последовательность {xn}, xn+1=j(xn), n=0, 1, 2, …, сходящаяся к корню x=c.

Теперь нам остаётся заметить, что итерационной последовательностью для уравнения (5.5), сходимость которой мы только что установили, является последовательность (3.5) метода касательных. Теорема доказана. 

Требование близости нулевого приближения x0 к искомому корню c является существенным для метода касательных. На рис.2.5 изображён график, где х0 выбрано неправильно, то есть расстояние сх0>ас, так как ас<bс. В результате чего х1 не принадлежит отрезку [a, b], и на этом процесс построения рекуррентной последовательности метода касательных обрывается.  

Таким образом, до начала расчётов по данному методу для выбора нулевого приближения х0 нужно знать область локализации искомого корня х=с. Если известен в общих чертах график функции f(x), то его легко определить по этому графику. В случае необходимости можно сделать несколько шагов по методу вилки. Затруднения, связанные с предварительным исследованием уравнения, вполне окупаются высокой скоростью сходимости метода.

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

рис. 2.5 Случай, когда процесс построения последовательности {xn} обрывается из-за плохого выбора нулевого приближения  

6. Первые приближения для метода касательных

Первые нулевые приближения для метода Ньютона, для итерационной последовательности, можно так же найти другим путём. Если нам известно, что функция f(x) на отрезке [a, b] непрерывна и дважды дифференцируема, и имеет ровно один корень, тогда можно взять за нулевое приближение значение одного из концов отрезка [a, b] в зависимости от знака второй производной, иначе при первом же приближении можно попасть за пределы отрезка [a, b] (рис. 1.6).

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

То есть можно сформулировать следующее правило:

Пусть в точках a и b функция f(x) имеет различные знаки, причём на отрезке [a, b] вторая производная положительна. Тогда за начальное приближение х1 надо выбирать ту из точек a или b, в которой функция f(x) принимает положительное значение. Если же на отрезке [a, b] вторая производная отрицательна, то за начальное приближение x1 надо выбирать ту точку, в которой функция f(x) принимает отрицательное значение.

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

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

В методе Ньютона (касательных) требуется вычислять производную функции, что не всегда удобно. Можно заменить производную функции первой разделённой разностью, найденной по двум последним итерациям, т. е. заменить касательную секущей. Тогда вместо процесса Приближённые методы решения алгебраического уравнения получим: 

Приближённые методы решения алгебраического уравнения (1.7)

для начала процесса необходимо задать х0 и х1 (рис. 1.7). Такие процессы, где для вычисления очередного приближения надо знать два предыдущих, называют двух шаговыми.   

Эти изменения сильно меняют характер итераций. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и малой окрестности корня. Скорость сходимости также изменяется. Его можно оценить, разлагая все функции в (1.7) по формуле Тейлора с центром Приближённые методы решения алгебраического уравнения. Получим с точностью до бесконечно малых более высокого порядка:

Приближённые методы решения алгебраического уравнения Приближённые методы решения алгебраического уравнения (2.7)

Решение этого рекуррентного соотношения естественно искать в виде аналогичном методу Ньютона: Приближённые методы решения алгебраического уравнения. Подставляя эту форму в соотношение (2.6), получим: 

ab=1, b2 - b - 1 = 0 (3.7)

Только положительный корень b квадратного уравнения (3.6) соответствует убыванию ошибки, т. е. сходящемуся процессу. Следовательно, в методе секущих

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

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

в то время как в методе Ньютона ошибка убывает быстрей (соответствуя b=2). Но в методе на каждой итерации надо вычислять и функцию, и производную, а в методе секущих – только функцию. Поэтому при одинаковом объёме вычисления в методе секущих можно сделать вдвое больше итераций и получить более высокую точность. Что является более приемлемым при численных расчётах на ЭВМ, чем метод касательных.  

В знаменателе формулы (1.7) стоит разность значений функции. Вдали от корня это несущественно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение невелико. Приводить к общему знаменателю уравнение (1.7) не следует: может увеличится потеря точности в расчётах.  

От «разболтки» страхуются так называемым приёмом Гарвика. Выбирают не очень малое e, ведут итерации до выполнения |xn+ 1-xn|<e и затем продолжают расчёт до тех пор, пока | xn+ 1-xn | убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют.

8. Метод хорд, или линейной аппроксимации

Рассмотрим задачу решения уравнения (1.1) методом хорд.  

Этот метод состоит в следующем. График функции f(x) заменяется её хордой, т. е. отрезком соединяющий концевые точки графика функции f(x): точки (a, f(a)) и (b, f(b)). Абсцисса х1 точки пересечения этой хорды с осью Ох и рассматривается, как первое приближение искомого корня (рис 1.8). Далее берётся тот из отрезков [a, x1] и [x1, b], на концах которого, функция f(x) принимает значения разного знака (далее будет показано, что при сделанных предположениях f(x) ¹ 0 и, следовательно, такой отрезок всегда существует), и к нему применяется тот же приём; получается второе приближение корня х2 и т. д. В результате образуется последовательность хn, n=1, 2, … которая, как это будет показано, при сделанных ограничениях на функцию f(x), сходится к корню уравнения f(x).

Легко получить рекуррентные формулы для указанных чисел хn, n=1, 2,… Уравнение прямой, проходящее через крайние точки графика функции f(x) имеет вид:

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

Приближённые методы решения алгебраического уравнения (1.8)

Обозначим его правую часть через l(x), т. е. Запишем уравнение в виде:

y = l(x)

Найдём абсциссу х1 точки пересечения прямой (1.8) с осью Ох, т. е. Решим уравнение l(x)=0; получим: 

Приближённые методы решения алгебраического уравнения (2.8)

Легко убедится, что:

a < x1 < b (3.8)

Это, например, следует из строгой монотонности и непрерывности функции l(x) и того, что на концах отрезка [a, b] она принимает значения разного знака: l(a)=f(a) и l(b)=f(b).

Аналогично находим

Приближённые методы решения алгебраического уравнения n=1, 2, … (4.8)

Покажем, что последовательность {xn} стремится к корню уравнения (1.0) монотонно.

Предположим для определённости, что f ¢(x) и f ¢¢(x) >0, a<x<b (рис 1.8). В этом случае функция f(x) строго монотонна и строго выпукла вниз. Следовательно, любая внутренняя точка хорды, соединяющей крайние точки графика функции f(x), лежит над соответствующей точкой графика функции f(x), т. е.

l(x) > f(x), a > x > b

В частности, если х0 корень уравнения (1.1): f(x0) = 0, отсюда следует, что

l(x0) > 0

C (3.8) и (4.8) получаем:

l(x) = 0, a > x1 > b

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

l(x1) < l(x0) (5.8)

но линейная функция l(x) строго монотонно возрастает, так как

l(b) = f(b) > f(a) = l(a)

поэтому из (5.8) следует x1 < x0 , заменяя теперь отрезок [a, b] отрезком [x1, b] и замечая, что f(x1) < 0 , аналогично можно доказать, что x1 < x2 < x0, далее по индукции получим:

x1 < x2 < … < xn < … < x0,

Таким образом, последовательность {xn}, будучи монотонной, сходится. Пусть lim xn = c, при n®¥ . Переходя к пределу при n®¥ в равенстве (4.8) получим f(c)=0, т. е. последовательность {xn} сходится к корню уравнения (1.1).

Если | f ¢(x)|³m>0, a<x<b, то не трудно получить оценку погрешности сходимости последовательности {xn} через значения самой функции f(x) в точках xn. Действительно,

f(xn)= f(xn)- f(x0)= f ¢(xn)×(xn-x0),

xn<xn<x0, n = 1, 2, …,

Отсюда:

Приближённые методы решения алгебраического уравнения, n = 1, 2, …,

Остальные случаи, т. е. случаи:

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

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

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

рассматриваются аналогично разобранному (рис 2.8).

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

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

рис. 2.8

9. Усовершенствованный метод хорд

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

Приближённые методы решения алгебраического уравненияПриближённые методы решения алгебраического уравнения рис.1.9 а) б)   

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

Приближённые методы решения алгебраического уравнения (1.9)

При этом а1 вычисляется по формуле:

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

а а2 в зависимости от знаков f(a), f(b), f(a1), если f(a)<0, f(b)>0,

Приближённые методы решения алгебраического уравнения , f(a1)<0

Приближённые методы решения алгебраического уравнения , f(a1)>0

Если случайно окажется, что точка а3, вычисленная по формуле (1.9), лежит за пределами отрезка [a, b], то на следующем шаге надо вместо этой точки взять ближайший к ней конец этого отрезка (рис. 1.9, б). Оказывается, что сходимость усовершенствованного метода хорд гораздо быстрее, чем у обычного. Именно, если x - корень уравнения f(x)=0, то:

|an+ 1|<C×|an-x| S, где

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: