Реферат: Методы решения алгебраических уравнений

Методы решения алгебраических уравнений

1. Одношаговые итерационные модели

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

Суть этого класса методов можнораскрыть на примере.

Пусть нам нужно решить уравнение:

/> (1)

для решения этого уравнениястроится соответствующая итерационная формула:

/> (2)

Задавая начальное приближениекорня уравнения (1) в виде:

/> (3)

находим дальнейшие приближенияпо формуле (2):

/> (4),/> (5), /> (6)

Мы видим, что каждое вычисленноезначение /> становится исходным длявычисления последующих приближений />.

Такие итерационные формулыназываются одношаговыми.

Существуют и двухшаговые,трёхшаговые и т.д. итерационные формулы, которые определяются соответственно формулами:

/> 

— двухшаговая формула (7)

/>

— трёхшаговые формула (8)

и т.д.

После построения итерационнойформулы (2) возникают вопросы:

а) сколько нужно считатьпоследовательных приближений />, т.е. когдаостановиться?

б) сходится липоследовательность приближений /> к корню/>?

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

а) задаётся точность вычислений /> и итерационный процессостанавливают, как только достигается соответствующая абсолютная погрешность, т.е.как только выполняется условие:

/> (9)

б) нужно соответствующим образомстроить формулы (2), используя соответствующие теоремы о достаточном условиисходимости. В частности теорему Банаха о сжатых отображениях.

Определение: Пусть M — метрическое пространство сметрикой />. Оператор A, отображающий это пространство в себя называется сжимающим,если существует такое число />, чтодля любой пары элементов /> имеетместо неравенство:

/> (10)

Т.о. сжимающий оператор сжимаетрасстояние между элементами /> и />, т.е. расстояние междуобразами элементов /> меньше или равнорасстоянию между их прообразами /> и />. Для таких отображенийиспользуется теорема Банаха. Теорема Банаха: Пусть A — сжимающий оператор в полном метрическом пространстве M, тогда уравнение

/> (11)

имеет в этом пространстве одно итолько одно решение, т.е. существует ровно один элемент />, для которого выполняетсяуравнение />. Этот элемент может бытьполучен как предел последовательности элементов />

/> (12)

где />,причём элемент /> может бытьвыбран произвольно. Эта теорема применима и для случая, когда оператор /> - является функцией, т.е. дляформулы (2), а также для построения сходящихся итерационных формул Ритца-Якобив случае линейных систем алгебраических уравнений с плохо обусловленнойматрицей (определитель близок к нулю) коэффициентов, для дифференциальных иинтегральных операторов и т.д. Для итерационной формулы (2), применяя формулуЛагранжа о конечных приращениях, получаем, что для /> имеетместо соотношение:

/> (13)

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

/> (14)

если Чебышевская норма функций />, т.е. если

/> (15)

В таком случае отображение /> из (2) является сжимающими, соответственно, для неё имеет место теорема Банаха.Т. е. итерационнаяформула (2) позволяет найти корень /> уравнения(1) по формуле

/> (16)

Несмотря на кажущуюся простоту,итерационные формулы вида (2) таят в себе много интересных эффектов. Дляраскрытия некоторых из них рассмотрим простейшую нелинейную итерационнуюформулу, возникающую в задаче об эволюции денежных вкладов.

2. Возникновение хаоса в детерминированных системах

Пусть /> - количество денежныхвкладов за /> лет. Коэффициентотносительного прироста вкладов обозначим через />.Тогда имеем:

/> (17)

т.е. />,где /> (18)

Для исследования динамикипроцесса перепишем (18) в виде:

/> (19)

Ясно, что если начальноезначение денежного вклада было />, тогда

/> (20)

из (20) следует, что с ростом n, количество денежных вкладов неограниченно увеличивается, т.к/>.

Формула (20) позволяет решитьзадачу о допустимых процентах роста R. Например,выясним, каким должен быть R, чтобы удвоение вкладовпроисходило за 50 лет. Имеем:

/> (21)

Тогда

/> (22)

т.е.

/> (23)

Теперь допустим, что советдиректоров банка решил увеличить коэффициент прироста R — для привлечения клиентов, но чтобы защитить себя отбанкротства решил не допускать дальнейшего увеличения вкладов если величинадостигает значения />, после чегокоэффициент должен становится отрицательным, т.е. уменьшать вклады пока неопустятся ниже />, для этогорешили, что />. Тогда из (17) получаем:

/> (24)

где />.Тогда имеем:

/> (25)

Исследуем точки равновесиясистемы (25), т.е. те значения вкладов />,которые с ростом n, не изменяются (или иначе />).

Очевидно, что такими значениямислужат:

а) /> иб) />.

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

а) Рассмотрим сначала состояниеравновесия />, т.е. состояние, когда навашем счету денег нет.д.обавим малое «возмущение» точке равновесия /> и исследуем её динамику современем: т.е. />, тогда из (25) получаем:

/> (27)

т.к />,ясно, что /> поэтому ею можнопренебречь в (27). Вследствии имеем:

/> (29)

отсюда, легко получить, что

/> (29)

т.е. возмущения нарастают современем, что со своей стороны означает неустойчивость точки равновесия />. По смыслу же, задачи этоозначает рост вклада со временем, если хоть какая-то малая сумма денег /> села на счёт.

б) Исследуем теперь устойчивостьвторой точки равновесия: />. Здесьтакже дадим малое приращение /> к точкеравновесия, т.е. рассмотрим значение /> иисследуем динамику этого состояния с течением времени n.Из (25) получаем:

/> (30)

Произведя преобразования, имеем:

/>

Учитывая, что /> и поэтому, пренебрегая еюполучаем:

/>

/> (31)

для устойчивости точкиравновесия />, должно выполнятся условие:

/> (32)

т.е.

/>

(рис.1)

/> (33)

это условие со своей стороныозначает, что

/> (34)

таким образом, если мы выберем вкачестве относительного коэффициента роста:

 /> 

(рис.2)

/> (35)

то состояние /> будет устойчивым, иначе мывступаем в зону неустойчивостей, которая полна неожиданностями. В частности,при />, (рис.3) возникаютпериодические колебания /> (рис.1).При /> картина усложняется ипоявляется двоякопериодические колебания (рис.2) При дальнейшем ростеотносительного коэффициента прироста, получаем учетверение периода и т.д., вслучае /> наблюдаются хаотическиеколебания (рис.3).

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

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

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

3. Методы решения алгебраических уравнений

Большинство задач физики,экономики, социологии, биологии и других областей знания приводят к решениюалгебраических уравнений или систем уравнений.

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

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

а) отделение корней, т.е. отысканиедостаточно малых областей в каждой из которых находится корень;

б) вычисление корней с заданнойточностью.

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

Перед началом решения уравнения

/> (36)

мы должны выделить интервалпоиска решения />, т.е. ответитьна вопрос а) предыдущего параграфа. Для этого используется теорема Вейерштрасса.

Теорема Вейерштрасса: Если наконцах некоторого отрезка непрерывная функция /> принимаетзначения разных знаков, то на этом отрезке уравнение (36) имеет хотя бы одинкорень.

/>

Эта теорема выражаетгеометрически очевидный факт (рис.4), состоящий в том, что если в точках /> и /> график непрерывной функциинаходится в

разных полуплоскостях от оси />, то найдётся точка />, такая что график этойфункции пересекается с осью /> в точке/>, т.е. />.

а /> b Замечание: если при этом /> имеет первую

производную /> - не меняющую знака, токорень единственный.

Таким образом, мы можем сказать,что уже умеем

Рис. находить отрезок />, где находится корень

уравнения (36), но этот отрезокможно уменьшать, основываясь на теореме Вейерштрасса.

Для этого в качестве первогоприближения к корню берём середину отрезка />,т.е.

/> (38)

Этой точкой отрезок /> делится на два равныхотрезка: /> и />. Используя теоремуВейерштрасса, устанавливаем в каком из этих отрезков лежит корень, т.е. наконцах какого из этих двух отрезков функция /> принимаетразные знаки. С этим отрезком действуем также, т.е. выбираем в качестве второгоприближения к корню середину этого отрезка /> ипродолжаем этот итерационный процесс, пока отрезок поиска решения /> не станет меньше требуемойточности />.

Оценка погрешности вычислений пометоду деления отрезка пополам производится по очевидной формуле:

/> (39)

Ясно, что />, а относительнаяпогрешность />.

Изложенный метод легкопрограммируется и даёт сходимость с точностью (39), хотя при практическихвычислениях чаще пользуются комбинациями различных численных методов, добиваясьболее быстрой сходимости процесса.

3.2 Метод ложного положения (метод хорд).

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

Для иллюстрации алгоритма методаложного положения (метода хорд), рассмотрим рис.5.

/>

рис.5.

Сначала находим отрезок /> где

yзаведомоизвестно, что существует

корень />, т.е. />, для этого по теоремеВейерштрасса должно быть />.

/>

/> /> /> />

В качестве первого приближения ккорню берём />, второе приближение />. Для нахождения следующегоприближения соединяем эти две точки отрезком прямой. Точку пересечения этогоотрезка берём в качестве третьего приближения />,далее значение функции /> сравнивается с /> и />, где будут разные знаки, вдальнейшем используется именно тот отрезок вместо />,и т.д. Соответствующая итерационная формула имеет вид:

/> (40)

где /> и/>.

Ясно, что эта итерационнаяформула требует, чтобы />, атакже /> и />.

Точность вычисления корняметодом хорд оценивается неравенством

/> (41)

предельная относительнаяпогрешность:

/> (42)

где />.

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

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

В отличие от предыдущих методовздесь не требуется предварительно искать отрезок />,где />. Для решения уравнения

/> (43)

в методе Ньютона задаёмсятребуемой точностью /> (абсолютнаяпогрешность). Далее произвольно выбираем начальное приближение />. Считаем, что

/> (44)

для нахождения следующегоприближения />, где

/> (45)

воспользуемся формулой Тейлорадля />:

/> (46)

Отбрасывая члены разложения,содержащие производные выше первого порядка, получаем уравнение для определенияприближённого значения корня />:

/> (47)

т.е.

/> (48)

Зная />,новое, улучшенное значение /> находиманалогично

/> (49)

и вообще

/> (50)

Вычисления надо продолжать дотех пор, пока не достигнем требуемой абсолютной погрешности />:

/> (51)

Предельная относительнаяпогрешность равна:

/> (52)

Скорость сходимости итерационнойформулы Ньютона (50) оценивается неравенством:

/> (53)

Ясно, что скорость сходимостивыше, чем в методе хорд. Однако, здесь так же нужно иметь в виду, что />, а также /> и />, а эти условия труднопроверить, что и является отталкивающим фактором для исследователей. Крометого, для применения метода Ньютона, нужно достаточно точное знание начальногоприближения />.

Здесь, так же как и в методехорд, легко представить этот процесс геометрически. Взяв начальное приближение />, в этой точке проводитсякасательная к графику функции />. Пересечениекасательной с осью абсцисс /> принимаетсяза первое приближение. Далее касательная проводится в точке />, пересечение касательной сосью /> берётся в качестве второгоприближения и т.д.

Литература

1. Высшая математика — Сапунов И.С. — М. 2000 г.