Задача о нахождении решений системы из n нелинейных алгебраических или трансцендентных уравнений сn неизвестными вида

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

В векторных обозначениях систему (6.1) можно записать в более компактной форме

вектор столбец функций, символом () T обозначена операция транспони-

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

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

Метод простой итерации для систем нелинейных уравнений по существу является обобщением одноименного метода для одного уравнения. Он основан на том, что система уравнений (6.1) приводится к виду

x 1= g 1(x 1, x 2, … , x n ) , x 2= g 2(x 1, x 2, … , x n ) ,

……………………

x n= g n(x 1 , x 2 , … , x n) ,

и итерации проводятся по формулам

x 1 (k + 1 )= g 1 (x 1 (k ), x 2 (k ), … , x n (k )) , x 2 (k + 1 )= g 2 (x 1 (k ), x 2 (k ), … , x n (k )) ,

……………………………

x n (k + 1 )= g n (x 1 (k ), x 2 (k ), … , x n (k )) .

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

(x 1 (0 ) ,x 2 (0 ) ,… ,x n (0 ) ) и продолжаются до тех пор, пока модули приращений

всех аргументов после одной k- итерации не станут меньше заданной величиныε :x i (k + 1 ) − x i (k ) < ε дляi = 1,2,… ,n .

Хотя метод простой итерации прямо ведет к решению и легко программируется, он имеет два существенных недостатка. Один из них – медленная сходимость. Другой состоит в том, что если начальное приближение выбрано далеко от истинного решения (X 1 ,X 2 ,… ,X n ) , то сходимость

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

Решить систему нелинейных уравнений:

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

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

Метод Ньютона

В случае одного уравнения F (x ) = 0 алгоритм метода Ньютона был легко получен путем записи уравнений касательной к кривойy = F (x ) . В основе метода Ньютона для систем уравнений лежит использование разложения функцийF 1 (x 1 ...x n ) в ряд Тейлора, причем члены, содержа-

щие вторые (и более высоких порядков) производные, отбрасываются. Пусть приближенные значения неизвестных системы (4.1) равны со-

ответственно a 1 ,a 2 ,....,a n . Задача состоит в нахождении приращений (по-

Проведем разложение левых частей уравнений (4.1) с учетом разложения в ряд Тейлора, ограничиваясь лишь линейными членами относи-

Подставляя в систему (4.1), получим следующую систему линейных алгебраических уравнений относительно приращений:

x 2 = a 2 , …x n = a n .

Определителем системы (4.3) является якобиан:

… … … …

∂ F n… … ∂ F n∂ x 1 ∂ x n

x 1= a 1,

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

Таким образом, итерационный процесс решения системы уравнений методом Ньютона состоит в определении приращений x 1 ,x 2 , ...,x n к значениям неизвестных на каждой итерации путем решения системы линейных алгебраических уравнений (4.3). Счет прекращается, если все приращения становятся малыми по абсолютной величине: maxx i < ε . В ме-

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

В качестве примера рассмотрим использование метода Ньютона для решения системы двух уравнений:

∂ ∂ F 1. x

Величины, стоящие в правой части, вычисляются при x = a ,y = b .

Например:

Поставим задачу отыскать действительные корни данного уравнения.

А таковые точно есть! – из статей о графиках функций и уравнениях высшей математики вы хорошо знаете, что график функции-многочлена нечётной степени хотя бы один раз пересекает ось , следовательно, наше уравнение имеет по меньшей мере один действительный корень. Один. Или два. Или три.

Сначала напрашивается проверить, наличие рациональных корней. Согласно соответствующей теореме , на это «звание» могут претендовать лишь числа 1, –1, 3, –3, и прямой подстановкой легко убедиться, что ни одно из них «не подходит». Таким образом, остаются иррациональные значения. Иррациональный корень (корни) многочлена 3-й степени можно найти точно (выразить через радикалы) с помощью так называемых формул Кардано , однако этот метод достаточно громоздок. А для многочленов 5-й и бОльших степеней общего аналитического метода не существует вовсе, и, кроме того, на практике встречается множество других уравнений, в которых точные значения действительных корней получить невозможно (хотя они существуют).

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

Зададим для нашего примера точность . Что это значит? Это значит, что нам нужно отыскать ТАКОЕ приближённое значение корня (корней) , в котором мы гарантированно ошибаемся, не более чем на 0,001 (одну тысячную) .

Совершенно понятно, что решение нельзя начинать «наобум» и поэтому на первом шаге корни отделяют . Отделить корень – это значит найти достаточно малый (как правило, единичный) отрезок, которому этот корень принадлежит, и на котором нет других корней. Наиболее прост и доступен графический метод отделения корней . Построим поточечно график функции :

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

Рассмотренная схема получила естественное название – метод половинного деления . И недостаток этого метода состоит в скорости. Медленно. Очень медленно. Слишком много итераций придётся совершить, прежде чем мы достигнем требуемой точности. С развитием вычислительной техники это, конечно, не проблема, но математика – на то и математика, чтобы искать наиболее рациональные пути решения.

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

Данная касательная пересекла ось абсцисс в жёлтой точке, и обратите внимание, что на первом шаге мы уже почти «попали в корень»! Это будет первое приближение корня . Далее опускаем жёлтый перпендикуляр к графику функции и «попадаем» в оранжевую точку. Через оранжевую точку снова проводим касательную, которая пересечёт ось ещё ближе к корню! И так далее. Нетрудно понять, что, используя метод касательных, мы приближаемся к цели семимильными шагами, и для достижения точности потребуется буквально несколько итераций.

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

Пример 1

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

Перед вами «щадящая версия» задания, в которой сразу констатируется наличие единственного действительного корня.

Решение : на первом шаге следует отделить корень графически. Это можно сделать путём построения графика (см. иллюстрации выше) , но такой подход обладает рядом недостатков. Во-первых, не факт, что график прост (мы же заранее не знаем) , а программное обеспечение – оно далеко не всегда под рукой. И, во-вторых (следствие из 1-го) , с немалой вероятностью получится даже не схематичный чертёж, а грубый рисунок, что, разумеется, не есть хорошо.

Ну а зачем нам лишние трудности? Представим уравнение в виде , АККУРАТНО построим графики и отметим на чертеже корень («иксовую» координату точки пересечения графиков) :

Очевидное преимущество этого способа состоит в том, что графики данных функций строятся от руки значительно точнее и намного быстрее. Кстати, заметьте, что прямая пересекла кубическую параболу в единственной точке, а значит, предложенное уравнение и в самом деле имеет только один действительный корень. Доверяйте, но проверяйте;-)

Итак, наш «клиент» принадлежит отрезку и «на глазок» примерно равен 0,65-0,7.

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

Найдём первую и вторую производные функции :

и проверим левый конец отрезка:

Таким образом, ноль «не подошёл».

Проверяем правый конец отрезка:

– всё хорошо! В качестве начального приближения выбираем .

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

Процесс завершается при выполнении условия , где – заранее заданная точность вычислений. В результате за приближённое значение корня принимается «энное» приближение: .

На очереди рутинные расчёты:

(округление обычно проводят до 5-6 знаков после запятой)

Поскольку полученное значение больше , то переходим к 1-му приближению корня:

Вычисляем:

, поэтому возникает потребность перейти ко 2-му приближению:

Заходим на следующий круг:

, таким образом, итерации закончены, и в качестве приближённого значения корня следует взять 2-е приближение, которое в соответствии с заданной точностью нужно округлить до одной тысячной:

На практике результаты вычислений удобно заносить в таблицу, при этом, чтобы несколько сократить запись, дробь часто обозначают через :

Сами же вычисления по возможности лучше провестив Экселе – это намного удобнее и быстрее:

Ответ : с точностью до 0,001

Напоминаю, что эта фраза подразумевает тот факт, что мы ошиблись в оценке истинного значения корня не более чем на 0,001. Сомневающиеся могут взять в руки микрокалькулятор и ещё раз подставить приближенное значение 0,674 в левую часть уравнения .

А теперь «просканируем» правый столбец таблицы сверху вниз и обратим внимание, что значения неуклонно убывают по модулю. Этот эффект называют сходимостью метода, которая позволяет нам вычислить корень со сколь угодно высокой точностью. Но сходимость имеет место далеко не всегда – она обеспечивается рядом условий , о которых я умолчал. В частности, отрезок, на котором изолируется корень, должен быть достаточно мал – в противном случае значения будут меняться беспорядочным образом, и мы не сможем завершить алгоритм.

Что делать в таких случаях? Проверить выполнение указанных условий (см. выше по ссылке) , и при необходимости уменьшить отрезок. Так, условно говоря, если бы в разобранном примере нам не подошёл промежуток , то следовало бы рассмотреть, например, отрезок . На практике мне такие случаи встречались , и этот приём реально помогает! То же самое нужно сделать, если оба конца «широкого» отрезка не удовлетворяют условию (т.е. ни один из них не годится на роль начального приближения) .

Но обычно всё работает, как часы, хотя и не без подводных камней:

Пример 2

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

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

А поэтому решение начинаем со спасительного трюка: представим уравнение в виде и изобразим графики :


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

Алгоритм, как вы понимаете, нужно «провернуть» дважды. Но это ещё на самый тяжелый случай, бывает, исследовать приходится 3-4 корня.

1) С помощью критерия выясним, какой из концов отрезка выбрать в качестве начального приближения первого корня. Находим производные функции :

Тестируем левый конец отрезка:

– подошёл!

Таким образом, – начальное приближение.

Уточнение корня проведем методом Ньютона, используя рекуррентную формулу:
– до тех пор, пока дробь по модулю не станет меньше требуемой точности:

И здесь слово «модуль» приобретает неиллюзорную важность, поскольку значения получаются отрицательными:


По этой же причине следует проявить повышенное внимание при переходе к каждому следующему приближению:

Несмотря на достаточно высокое требование к точности, процесс опять завершился на 2-м приближении: , следовательно:

С точностью до 0,0001

2) Найдем приближённое значение корня .

Проверяем на «вшивость» левый конец отрезка:

, следовательно, он не годится в качестве начального приближения.

Метод Ньютона (также известный как метод касательных) - это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727), под именем которого и обрёл свою известность.

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas (лат.О б анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу , и в работе De metodis fluxionum et serierum infinitarum (лат.Метод флюксий и бесконечные ряды) или Geometria analytica (лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения x n , а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работеAnalysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений x n вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.

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

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

Рис.1 . График изменение функции

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

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

Условием окончания итерационного процесса является выполнение следующего условия:

где ˗ допустимая погрешность определения корня.

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

Математическое обоснование

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

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

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

Производная сжимающего отображения определяется в следующем виде:

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

С учетом этого сжимающая функция прием следующий вид:

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

Алгоритм нахождения корня нелинейного уравнения по методу

1. Задать начальную точку приближенного значения корня функции , а также погрешность расчета (малое положительное число ) и начальный шаг итерации ( ).

2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:

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

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

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

Пример решения уравнений

по методу Ньютона для уравнения с одной переменной

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

Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.

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

Рис.2 . Результаты расчета по методу Ньютона для уравнения с одной переменной

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

Рис.3 . Листинг программы в MathCad

Модификации метода Ньютона для уравнения с одной переменной

Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.

Упрощенный метод Ньютона

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

Разностный метод Ньютона

В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:

Двух шаговый метод Ньютона

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

В результате приближенное значение корня функции f(x) будет определяться следующим выражением:

где

Рис.5 . Двух шаговый метод Ньютона

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

• Назад
• Вперёд

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

Федеральное агентство по образованию

Сочинский государственный университет туризма и курортного дела

Факультет информационных технологий и математики

Кафедра общей математики

Курсовая работа по дисциплине

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

«Метод Ньютона и его модификации решения систем нелинейных уравнений»

Выполнила:

студентка 3 курса

группы 06-ИНФ

Лавренко М.В.

Проверил:

доцент, кандидат

педагогических наук

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

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

А так же коротко описываются: методы ложного положения, метод секущих, метод Стеффенсена, который чаще оказывается лучшим выбором для решения систем нелинейных уравнений нежели метод секущих или метод ложного положения.

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

1) Метод касательных.

Выведем расчётную формулу метода для решения нелинейного уравнения

Уравнение касательной, проведённой к графику функции

Полагая в равенстве (1.1)

Выражая из него

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

Пусть требуется решить систему уравнений

вещественнозначные функции п вещественных переменных

данную систему (2.1) можно записать одним уравнением

относительно векторной функции F векторного аргумента х. Таким образом, исходную задачу можно рассматривать как зада­чу о нулях нелинейного отображения

2) Метод линеаризации.

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«Приднестровский государственный университет им. Т.Г. Шевченко»

Рыбницкий филиал

Кафедра физики, математики и информатики

Курсовая работа

по дисциплине: «Практикум по решению задач на ЭВМ»

«Метод Ньютона для решения нелинейных уравнений»

Выполнила:

студентка III курса;

330 й группы

специальности: «Информатика

с доп. специальностью английский

Нистор А. Г..

Проверила:

преподаватель Панченко Т. А.

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

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

Численные методы разрабатывают и исследуют, как правило, высококвалифицированные специалисты-математики. Для большинства пользователей главной задачей является понимание основных идей и методов, особенностей и областей применения. Однако, пользователи хотят работать с ЭВМ не только как с высокоинтеллектуальным калькулятором, а еще и как с помощником в повседневной работе, хранилищем информации с быстрым и упорядоченным доступом, а так же с источником и обработчиком графической информации. Все эти функции современной ЭВМ я предполагаю продемонстрировать в настоящей курсовой работе.

Цели и задачи.

Целью данной курсовой работы является изучение и реализация в программном продукте решения нелинейных уравнений при помощи метода Ньютона. Данная работа состоит из трёх разделов, заключения и приложения. Первый раздел - теоретический и содержит общие сведения о методе Ньютона. Второй – это практическая часть. Здесь описывается метод Ньютона разобранный на конкретных примерах. Третий посвящён тестированию программы и анализу получившихся результатов. В заключении представлен вывод о проделанной работе.

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

Для этого необходимо выполнить следующие задачи:

1. Изучить необходимую литературу.

2. Обзорно рассмотреть существующие методы по решению нелинейных уравнений.

3. Изучить метод Ньютона для решения нелинейных уравнений.

4. Рассмотреть решение нелинейных уравнений методом Ньютона на конкретных примерах.

5. Разработать программу для решения нелинейных уравнений методом Ньютона.

6. Проанализировать получившиеся результаты.

Рассмотрим задачу нахождения корней нелинейного уравнения

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

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

Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано:

f(a)*f(b)<0 (2)

При этом подразумевается, что функция f(x) непрерывна на данном отрезке. Однако данное условие не отвечает на вопрос о количестве корней уравнения на заданном отрезке . Если же требование непрерывности функции дополнить ещё требованием её монотонности, а это следует из знакопостоянства первой производной , то можно утверждать о существовании единственного корня на заданном отрезке.

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

где вещественные коэффициенты.

а) Уравнение степени n имеет n корней, среди которых могут быть как вещественные, так и комплексные. Комплексные корни образуют комплексно-сопряженные пары и, следовательно, уравнение имеет четное число таких корней. При нечетном значении n имеется, по меньшей мере, один вещественный корень.

б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов . Замена х на –х в уравнении (3) позволяет таким же способом оценить число отрицательных корней.

На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью . Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения . Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие:

, (4)

где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях.

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

или малости невязки:

Эта работа посвящена изучению алгоритма решения нелинейных уравнений с помощью метода Ньютона.

1.1 Обзор существующих методов решения нелинейных уравнений

Существует много различных методов решения нелинейных уравнений, некоторые из них представлены ниже:

1)Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x 0 и точность ε. Первое приближение решения x 1 находим из выражения x 1 =f(x 0), второе - x 2 =f(x 1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>ε. Условие сходимости метода итераций |f"(x)|<1.

2)Метод Ньютона . При решении нелинейного уравнения методом Ньтона задаются начальное значение аргумента x 0 и точность ε. Затем в точке(x 0 ,F(x 0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x 1 . В точке (x 1 ,F(x 1)) снова строим касательную, находим следующее приближение искомого решения x 2 и т.д. Указанную процедуру повторяем пока |F(xi)| > ε. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой x i+1 =x i -F(x i)\ F’(x i). Условие сходимости метода касательных F(x 0)∙F""(x)>0, и др.

3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле С к =а к +в к /2.

Для того чтобы выбрать из двух получившихся отрезков необходимый, надо находить значение функции на концах получившихся отрезков и рассматривать тот на котором функция будет менять свой знак, то есть должно выполняться условие f (а к)* f (в к)<0.

Процесс деления отрезка проводится до тех пор, пока длина текущего интервала неопределённости не будет меньше заданной точности, то есть

в к – а к < E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.

4). Метод хорд . Идея метода состоит в том, что на отрезке строится хорда стягивающая концы дуги графика функции y=f(x), а точка c, пересечения хорды с осью абсцисс, считается приближенным значением корня

c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),

c = b - (f(b)Ч (a-b)) / (f(a) - f(b)).

Следующее приближение ищется на интервале или в зависимости от знаков значений функции в точках a,b,c

x* О , если f(с)Ч f(а) > 0 ;

x* О , если f(c)Ч f(b) < 0 .

Если f"(x) не меняет знак на , то обозначая c=x 1 и считая начальным приближением a или b получим итерационные формулы метода хорд с закрепленной правой или левой точкой.

x 0 =a, x i+1 = x i - f(x i)(b-x i) / (f(b)-f(x i), при f "(x)Ч f "(x) > 0 ;

x 0 =b, x i+1 = x i - f(x i)(x i -a) / (f(x i)-f(a), при f "(x)Ч f "(x) < 0 .

Сходимость метода хорд линейная.

1.2 Алгоритм метода Ньютона

Построим эффективный алгоритм вычисления корней уравнения. Пусть задано начальное приближение . Вычислим в этой точке значение функции и её производной . Рассмотрим графическую иллюстрацию метода:

.

(8)

Продолжая этот процесс, получим известную формулу Ньютона:

(9)

Приведем простейшую рекурсивную подпрограмму-функцию:

function X_Newt(x,eps:real):real;

y:=x-f(x)/f1(x);

if abs(f(x)) > eps

then X_Newt:=X_Newt(y,eps)

Метод Ньютона (касательных) характеризуется квадратичной скоростью сходимости, т.е. на каждой итерации удваивается число верных знаков. Однако этот метод не всегда приводит к нужному результату. Рассмотрим этот вопрос подробнее.

Преобразуем уравнение (1) к эквивалентному уравнению вида:

В случае метода касательных . Если известно начальное приближение к корню x=x 0 , то следующее приближение найдем из уравнения x 1 =g(x 0), далее x 2 =g(x 1),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерации

x k+1 =g(x k) (11)

Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7).

Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода.

Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие , то процесс сходится, иначе – расходится (рис3(б)).

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

Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x . Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1

Метод Ньютона обладает высокой скоростью сходимости, однако он не всегда сходится. Условие сходимости , где g(x) = x – f(x)/ f’(x), сводится к требованию .

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

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

(13)

Другой метод модификации – замена производной конечной разностью

(14)

Тогда (15)

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

Запишем в общем виде алгоритм метода Ньютона.

1. Задать начальное приближение х (0) так, чтобы выполнилось условие

f(x (0))*f’’(x (0))>0. (16)

Задать малое положительное число ε , как точность вычислений. Положить к = 0.

2. Вычислить х (к+1) по формуле (9) :

.

3. Если | x (k+1) - x (k) | < ε, то процесс вычисления прекратить и положить х* = x (k+1) . Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.

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

Пример 1

sin x 2 + cosx 2 - 10x. = 0.

F’(x)=2x cosx 2 - 2x sinx 2 - 10.

F’’(x)=2cosx 2 - 4x 2 sinx 2 - 2sinx 2 - 4x 2 cosx 2 = cosx 2 (2-4x 2) - sinx 2 (2+4x 2).

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0.

Пусть x (0) = 0, 565, тогда f(0. 565)*f’’(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0,

Условие выполняется, значит берём x (0) = 0, 565.

Отсюда следует, что корень уравнения х = 0, 101.

Пример 2

Решить уравнение методом Ньютона.

cos x – e -x2/2 + x - 1 = 0

Вычисления производить с точностью ε = 0, 001.

Вычислим первую производную функции.

F’(x) = 1 – sin x + x*e -x2/2 .

Теперь вычислим вторую производную от функции.

F’’(x) = e -x2/2 *(1-x 2) – cos x.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0.

Пусть x (0) = 2, тогда f(2)*f’’(2) = 0. 449 * 0. 010 = 0.05 > 0,

Условие выполняется, значит берём x (0) = 2.

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

Отсюда следует, что корень уравнения х = 1. 089.

Пример 3

Решить уравнение методом Ньютона.

Вычисления производить с точностью ε = 0, 001.

Вычислим первую производную функции.

F’(x) = 2*x + e -x .

Теперь вычислим вторую производную от функции.

F’’(x) = 2 - e -x .

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0.

Пусть x (0) = 1, тогда f(2)*f’’(2) = 0. 632 * 1, 632 = 1, 031 > 0,

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

Отсюда следует, что корень уравнения х = 0, 703.

Решить уравнение методом Ньютона.

cos x –e -x/2 +x-1=0.

Вычислим первую производную функции.

F’(x) = -sin x + e -x/2 /2+1.

Теперь вычислим вторую производную от функции.

F’’(x) = -cos x - e -x/2 /4.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0.

Пусть x (0) = 1, тогда f(2)*f’’(2) = -0. 066 * (-0. 692) = 0. 046 > 0,

Условие выполняется, значит берём x (0) = 1.

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

Отсюда следует, что корень уравнения х = 1. 162.

Пример 5

Решить уравнение методом Ньютона.

2+e x - e -x =0.

Вычислим первую производную функции.

F’(x) = e x +e -x .

Теперь вычислим вторую производную от функции.

F’’(x) = e x -e -x .

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0.

Пусть x (0) = 1, тогда f(2)*f’’(2) = 0. 350 * 2, 350 = 0. 823 > 0,

Условие выполняется, значит берём x (0) = 1.

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

Отсюда следует, что корень уравнения х = 0, 881.

3.1 Описание программы

Данная программа создана для работы в текстовом и графическом режиме. Она состоит из модуля Graph, Crt, трёх функций и трёх процедур.

1. модуль Crt предназначен для обеспечения контроля над текстовыми режимами экрана, расширенными кодами клавиатуры, цветами, окнами и звуком;

2. модуль Graph предназначен для обеспечения контроля над графическими объектами;

3. procedure GrafInit - инициализирует графический режим;

4. function VF – вычисляет значение функции;

5. function f1 – вычисляет значение первой производной функции;

6. function X_Newt – реализует алгоритм решения уравнения методом Ньютона.

7. procedure FGraf – реализует построение графика заданной функции f(x);

Ots=35 - константа, определяющая количество точек для отступа от границ монитора;

fmin, fmax – максимальные и минимальные значения функции;

SetColor(4) – процедура, которая устанавливает текущий цвет графического объекта, используя палитру, в данном случае это красный цвет;

SetBkColor(9) – процедура, которая устанавливает текущий цвет фона, используя палитру, в данном случае – это светло-синий цвет.

8. Procedure MaxMinF – вычислят максимальные и минимальные значения функции f(x).

Line – процедура, которая рисует линию из точки с координатами (x1, у1) в точку с координатами (х2, у2);

MoveTo – процедура, перемещающая указатель (СР) в точку с координатами (х, у);

TextColor(5) – процедура, устанавливающая текущий цвет символов, в данном случае – это розовый;

Outtexty(х, у, ‘строка’) – процедура, которая выводит строку, начиная с позиции (х, у)

CloseGraph – процедура, закрывающая графическую систему.

3.2 Тестирование программы

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

1) sin x 2 + cosx 2 - 10x. = 0.

Введите а = -1

Введите b=1

= [-1, 1]

{вывод графика функции}

Получим: х=0, 0000002

2) cos x – e -x2/2 + x - 1 = 0.

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке .

Введите а = -3

Введите b=3

= [-3, 3]

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим: х=-0, 0000000

3) x 2 - e -x = 0.

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке .

Введите а = -1

Введите b=1

= [-1, 1]

Введите точность вычисления eps=0. 01

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим: х=0, 0000000

4) cos x –e -x/2 +x-1=0.

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке .

Введите а = -1,5

Введите b=1,5

= [-1,5, 1,5 ]

Введите точность вычисления eps=0. 001

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим: х=0, 0008180

5) -2+e x - e -x =0.

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке .

Введите а = -0,9

Введите b=0,9

= [-0,9, 0,9]

Введите точность вычисления eps=0. 001

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:

Сделаем проверку, подставив полученный ответ в уравнение.

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

1.Изучена необходимая литература.

2.Обзорно рассмотрены существующие методы по решению нелинейных уравнений.

3.Изучен метод Ньютона для решения нелинейных уравнений.

4.Рассмотрено решение нелинейных уравнений методом Ньютона на примере.

5.Проведены тестирование и отладка программы.

Список используемой литературы

1. Б.П. Демидович, И.А Марон. Основы вычислительной математики. – Москва, изд. «Наука»; 1970.

2. В.М. Вержбицкий. Численные методы (линейная алгебра и нелинейные уравнения). – Москва, «Высшая школа»; 2000.

3. Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков. Численные методы в задачах и упражнениях. – Москва, «Высшая школа»; 2000.

4. Мэтьюз, Джон, Г.,Финк, Куртис, Д. Численные методы MATLAB, 3-е издание.- Москва, «Вильяс»; 2001.