Численные методы решения уравнений метод ньютона. Метод касательных

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

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

Основное достоинство метода – он обладает быстрой сходимостью.

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

Рассмотрим нелинейное уравнение в общем виде:

Искомое решение уравнения – точка, в которой кривая пересекает ось абсцисс.

Задаем начальное приближение неиз-вестной х (0) . Определяем значение функции в этой точке w(х (0)) и проводим касательную к кривой в точке В. Точка пересечения этой касательной с осью абсцисс определяет сле-дующее приближение неизвестной х (1) и т.д.

Разложим уравнение (1) в ряд Тейлора в окрестностях точки х (0) . Рас-смотрим члены разложения, содержащие только 1-ю производную:

(2)

х – х (0) = Δх - поправка к неизвестной. Если определим её, то сможем определить и следующее приближение.

Из (2) определяем поправку (3)

Тогда следующее приближение: (5)

Аналогично получаем к -е приближения:

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

Формулу (6) можно получить другим способом из рисунка:

Итерационный процесс сходится, если уменьшается и приближается к 0 . Результат достигнут, если .

Комментарий к геометрической интерпретации

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

Пример:

Пример:

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

Простой способ определения области расположения корней - табуляция .

Итерационный процесс Ньютона не сходится , если начальные приближения выбраны так, что:

Процесс или не сходится или сходится очень плохо.

Метод Ньютона-Рафсона для решения СНАУ

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

При этом, для решения систем нелинейных уравнений нужно вместо од-ной неизвестной рассматривать совокупность(вектор) неизвестных :

вместо одной невязки уравнения, рассматриваем вектор невязок уравнений системы:

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

Рассмотрим систему действительных нелинейных алгебраических уравне-ний:

(7)

В матричном виде ее можно записать:

где Х = х 2 – вектор – столбец неизвестных;

w 1 (х 1 , х 2 , … х n)

W = w 2 (х 1 , х 2 , … х n) – вектор-функция.

w n (х 1 , х 2 , … х n)

Пусть - начальные приближения неизвестных. Разложим каждое уравнение системы (7) в ряд Тейлора в окрестности точки Х (0) , то есть выполним приближенную замену исходных нелинейных уравнений линей-ными, в которых сохраняется только 1-я производная (линеаризация). В ре-зультате система уравнений (7) принимает вид:

(9)

В результате получили систему линейных уравнений (линеаризованная система), в которой неизвестными являются поправки . Коэф-фициенты при неизвестных в этой системе – первые производные от урав-нений w j исходной нелинейной системы по всем неизвестным Х i . . Они обра-зуют матрицу коэффициентов – матрицу Якоби :

=

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

Запишем линеаризованную систему (9) в матричной форме:

(10)

Здесь - вектор невязок уравнений исходной системы. Его эле-менты получаем при подстановке в уравнения нелинейной системы очеред-ных приближений неизвестных;

- матрица Якоби . Ее элементами являются первые частные про-изводные от всех уравнений исходной системы по всем неизвестным;

- вектор поправок к искомым неизвестным. На каждой итерации он может быть записан:

Систему (10) с учетом принятых обозначений можно записать:

(12)

Эта система линейна относительно поправок ΔХ (к) .

Система (13) - линеаризованная система уравнений, которой заменяется исходная СНАУ на каждом шаге итерационного процесса.

Система (13) решается любым известным способом, в результате находим вектор поправок . Затем из (11) можем найти очередные приближения неизвестных:

Т.о. каждый шаг итерационного процесса состоит в решении линейной сис-темы (13) и определении очередного приближения из (14).

Из (11) и (12) можно получить общую рекуррентную формулу (в матричном виде), соответствующую методу Ньютона–Рафсона:

(15)

Она имеет структуру, соответствующую формуле (6).

Формула (15) в практических расчетах используется редко , так как здесь нужно обращать матрицу Якоби (большой размерности) на каждой итерации расчетов. В реальных расчетах поправки определяются в результате решения линейной системы (13).

Контроль завершения итерационного процесса выполняем по вектору невязок:

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

Алгоритм решения СНАУ методом Ньютона-Рафсона

1. Задание вектора начальных приближений неизвестных .

Задание точности расчета є , других параметров расчета

2. Определение невязок нелинейных уравнений в точке приближения ;

2.3. Определение элементов матрицы Якоби в точке очередного прибли-жения неизвестных ;

2.4. Решение линеаризованной системы (13) любым известным методом. Определение поправок к неизвестным .

2.5. Определение очередного приближения неизвестных в соответ-ствии с (14).

2.6. Контроль завершения итерационного процесса в соответствии с (16). Если условие не выполняется, то возврат к пункту 2.

Примерчик:

Решить СЛАУ методом Ньютона-Рафсона:

(решение Х 1 =Х 2 =2)

Запишем уравнения в виде невязок:

Определяем элементы матрицы Якоби:

Матрица Якоби:

Реализуем алгоритм метода Ньютона-Рафсона:

1) Первая итерация:

Начальные приближения

Невязки

Матрица Якоби:

Линеаризованная система уравнений:

1-е приближение неизвестных:

2) Вторая итерация

3) Третья итерация:

… ……… …… …… …… ……..

Решение систем уравнений установившегося режима методом Ньютона-Рафсона

Нелинейное уравнение установившегося режима в форме баланса мощ-ности для -го узла имеет вид:

(17)

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

Здесь -заданные мощности в узле;

Неизвестные составляющие напряжения в узлах. Их нужно

определить в результате расчета.

В правой части уравнений (18) - расчетная суммарная мощность пере-токов в ветвях, подходящих к -му узлу.

Запишем эти уравнения (18) в виде невязок :

Невязки уравнений (19) соответствует расчетному небалансу активной и реактивной мощности в -ом узле.

Невязки описывают режим узла і и являются нелинейными функциями от неизвестных напряжений в узлах . Нужно, чтобы -> 0.

Будем решать методом Ньютона-Рафсона систему 2n уравнений вида (19), то есть для решения задачи расчета установившегося режима электри-ческой сети методом Ньютона - Рафсона нужно:

1) сформировать систему 2n уравнений вида (19) для всех узлов электрической сети, кроме балансирующих;

2) организовать итерационный процесс метода Ньютона-Рафсона

для решения этой системы уравнений. В результате решения

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

Запишем эту систему уравнений в общем виде:

(20)

Получили систему 2 нелинейных уравнений невязок с 2 неизвест-ными, которыми. Неизвестными в ней являются составляющие напряжения - модули и углы .

Для решения системы (20) методом Ньютона-Рафсона нужно составить вспомогательную линеаризованную систему уравнений вида (13), решая ко-торую на каждой итерации, определяем поправки к неизвестным:

(21)

С учетом принятых обозначений система (21) может быть записана:

(22)

где -матрица Якоби, её элементами являются частные производные от уравнений системы (20) по всем неизвестным - составляющим напряже-ний

Вектор невязок уравнений системы (20). Их значения получаем при подстановке в уравнения очередных приближений неизвестных;

Вектор поправок к неизвестным:

; ΔӨ i = Ө i (к+1) - Ө i (к) , ΔU i = U i (к+1) - U i (к) .

Для определения элементов матрицы Якоби применяем аналитическое дифференцирование , т.е. дифференцируем каждое уравнение системы (20) по искомым величинам – углам и модулям напряжений. Чтобы сформировать матрицу Якоби, нужно получить аналитические выражения для производных следующих видов :

1) Производная от уравнения невязки активной мощности го узла по углу напряжения этого же узла: ;

2) Производная от уравнения невязки активной мощности го узла по углу напряжения смежного j- го узла: ;

3) Производная от невязки активной мощности го узла по модулю напряжения этого же узла: ;

4) Производная от невязки активной мощности го узла по модулю напряжения смежного узла: ;

Аналогично определяются ещё четыре вида производных – производные от уравнений невязки реактивной мощности го узла по всем неизвестным:

5) ; 6) ; 7) ; 8) .

С учетом этих производных матрицу Якоби можно записать в общем виде:

(23)

Определим аналитические выражения для производных, дифференци-руя уравнения системы (20) по неизвестным величинам. Они имеют вид:

(24)

Матрица Якоби в общем случае - квадратная матрица, симметричная, размерностью , её элементами являются частные производные от невязок уравнений (небаланса мощностей) по всем неизвестным.

Если узлы не связаны между собой, то соответствующие произ-водные в матрицы матрице Якоби, расположенные вне диагонали, будут равны нулю (аналогично матрице проводимостей) – т.к. в соответствующих форму-лах (24) взаимная проводимость y ij является сомножителем и. y ij =0.

Каждая строка матрицы – это производные от очередного уравнения системы (20).

Наличие в схеме моделируемой сети особых узлов (опорные и балансирую-щие узлы, узлы ФМ) сказывается на структуре системы уравнений устано-вившегося режима и на структуре матрицы Якоби:

1. Для узлов с фиксацией модуля напряжения (ФМ), в которых заданы и неизвестными являются и , из матрицы Якоби исключается стро-ка производных (т.к. Q i не задана, то и уравнение баланса реак-тив-ной мощности (18), (19) составить нельзя) и столбец производных (т.к. модуль напряжения U i известен и он исключается из состава неизвест-ных).

2. Для узлов опорных и балансирующих – соответствующие строки и столбцы матрицы исключаются;

3. Если узлы не связаны непосредственно – соответствующие произ-водные в матрице равны нулю.

Матрицу Якоби можно разбить на четыре блока :

1) - производные от уравнений небаланса активной мощности (20) по углам напряжений;

2) - производные от уравнений небаланса активной мощности по модулям напряжений;

3) - производные от уравнений небаланса реактивной мощности (20) по углам напряжений;

4) - производные от уравнений небаланса реактивной мощности по модулям напряжений.

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

С учетом этого, матрица Якоби может быть представлена в виде блочной мат-рицы:

Где субвектора неизвестных величин.

С учетом этого,Тогда линеаризованную систему уравнений (22) можно запи-сать в ви-де:

. (25)

Решая эту линейную систему уравнений (любым известным методом) на

кКаждой итерации метода, находим поправки к неизвестным , а затем и

очередные приближения неизвестных:

(26)

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

- · (27)

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

Алгоритм решения систем уравнений установившегося режима методом Ньютона - Рафсона

1. Задание начальных значений неизвестных напряжений . В ка-честве начальных приближений принимаем: , т.е. номинальные напряжения узлов;

2. Задание условий расчета: точность ε , предельное количество итера-ций , ускоряющие коэффициенты и др.

3. Определение невязок уравнений в соответствии с уравнениями (20) при очередных приближениях неизвестных;

4. Определение элементов матрицы Якоби в соответствии с (24) при очередных приближениях неизвестных;

5. Решение линеаризованной системы уравнений (25) и определение поправок к неизвестным ;

6. Определение очередных приближений неизвестных в соответствии с (26);

7. Проверка завершения итерационного процесса:

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

Если условие не выполняется, то возврат к пункту 3 и повторение рас-чета при новых приближениях неизвестных.

Существует ряд модификаций метода Ньютона-Рафсона. В том числе:

1. Модифицированный метод Ньютона-Рафсона.

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

2. Разделенный метод Ньютона-Рафсона.

Производные вида очень малы и их значениями можно прине-бречь. В результате, в матрице Якоби остаются два блока - 1-й и 4-й, и сис-тема (25), состоящая из уравнений, распадается на две независимые сис-темы размерностью . Каждая из этих систем решается отдельно от другой. Это приводит к сокращению объема вычислений и необходимой памяти ЭВМ.



Ключевые слова:

Цель работы: изучить методы решения нелинейных уравнений с одним неизвестным и апробировать их в опытно-экспериментальной работе.

Задачи работы:

1. Проанализировать специальную литературу и выбрать наиболее рациональные способы решения нелинейных уравнений, позволяющие глубоко изучить и усвоить данную тему всем выпускникам средней школы.
2. Разработать некоторые аспекты методики решения нелинейных уравнений с применением ИКТ.
3. Изучить методы решения нелинейных уравнений:

‒ Шаговый метод

‒ Метод деления пополам

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

Введение.

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

Шаговый метод.

Пусть требуется решить нелинейное уравнение вида уравнение F(x)=0. Предположим также, что нам задан некоторый интервал поиска . Требуется найти интервал [а,b] длиной h, содержащий первый корень уравнения, начиная с левой границы интервала поиска.

Рис. 1. Шаговый метод

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

I этап. Отделение корней.

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

• Подставляем значения X (желательно с каким-то достаточно мелким шагом) и смотрим где функция сменит знак. Если функция сменила знак, это значит, что на участке между предыдущим и текущим значением X лежит корень (если функция не меняет характер возрастания/убывания, то можно утверждать, что корень на этом интервале один).
• Графический метод. Строим график и оцениваем на каких интервалах лежит один корень.
• Исследуем свойства конкретной функции.

II этап. Уточнение корней.

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

Метод половинного деления

Быстрый и достаточно простой численный метод решения уравнений, основанный на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до того времени, пока не будет достигнута заданная точность Е. Данный метод обычно используется при решении квадратных уравнений и уравнений высших степеней. Однако у данного метода есть существенный недостаток - если на отрезке [а,b] содержится более одного корня, то с его помощью не удастся добиться хороших результатов.

Рис. 2. Метод дихотомии

Алгоритм данного метода следующий:

‒ Определить новое приближение корня х в середине отрезка [а;b]: х=(а+b)/2.

‒ Найти значения функции в точках а и х: F(a) и F(x).

‒ Проверить условие F(a)*F(x)

‒ Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие |F(x)|

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

Самый точный из численных методов решения; подходит для решения очень сложных уравнений, но усложняется необходимостью вычисления производных на каждом шаге. заключается в том, что если x n - некоторое приближение к корню уравнения , то следующее приближение определяется как корень касательной к функции f(x), проведенной в точке x n .

Уравнение касательной к функции f(x) в точке x n имеет вид:

В уравнении касательной положим y = 0 и x = x n +1 .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

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

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

Метод Ньютона (метод касательных) обычно применяется в том случае, если уравнение f(x) = 0 имеет корень , и выполняются условия:

1) функция y= f(x) определена и непрерывна при ;

2) f(a)·f(b) (функция принимает значения разных знаков на концах отрезка [a;b ]);

3) производные f"(x) и f""(x) сохраняют знак на отрезке [a;b ] (т. е. функция f(x) либо возрастает, либо убывает на отрезке [a;b ], сохраняя при этом направление выпуклости);

Смысл метода заключается в следующем: на отрезке [a;b ] выбирается такое число x 0 , при котором f(x 0) имеет тот же знак, что и f""(x 0), т. е. выполняется условие f(x 0)·f""(x) > 0 . Таким образом, выбирается точка с абсциссой x 0 , в которой касательная к кривой y=f(x) на отрезке [a;b ] пересекает ось Ox . За точку x 0 сначала удобно выбирать один из концов отрезка.

Рассмотрим данный алгоритм на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2– 2, непрерывная на отрезке (0;2), и имеющая f "(x) =2x>0 и f ""(x) = 2> 0 .

В нашем случае уравнение касательной имеет вид: y-y 0 =2x 0 ·(x-x 0). В качестве точки x 0 выбираем точку B 1 (b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B 1 , и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6. Ox: x 1 =

Рис. 3. Построение первой касательной к графику функции f(x)

y=f(x) Ox через точку x 1 , получаем точку В 2 =(1.5; 0.25) . Снова проводим касательную к функции y = f(x) в точке В 2 , и обозначаем точку пересечения касательной и Ox точкой x 2 .

Уравнение второй касательной: y-2.25=2*1.5(x-1.5), y = 3x - 4.25. Точка пересечения касательной и оси Ox: x 2 = .

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку В 3 и так далее.

Рис. 4. Построение второй касательной к графику функции f(x)

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

=

Третье приближение корня определяется по формуле:

Таким образом, i -ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства |xi-xi-1|

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

Решение уравнения при помощи САПР MathCAD

Для простейших уравнений вида f (x ) = 0 решение в MathСAD находится с помощью функции root .

root(f (х 1 , x 2 , … ) , х 1 , a, b ) - возвращает значение х 1 , принадлежащее отрезку [ a, b ] , при котором выражение или функция f (х ) обращается в 0. Оба аргумента этой функции должны быть скалярами. Функция возвращает скаляр.

Рис. 5. Решение нелинейного уравнения в MathCAD (функция root)

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

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

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

Рис. 6. Решение нелинейного уравнения в MathCAD (функция solve)

Заключение

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

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

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

Литература:

1. Митяков С. Н. Информатика. Комплекс учебно-методических материалов. - Н. Новгород: Нижегород. гос. техн. ун-т.,2006
2. Вайнберг М. М., Треногин В. А. Теория ветвления решений нелинейных уравнений. М.: Наука, 1969. - 527 с.
3. Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся ВТУЗов - М.: Наука, 1986.
4. Омельченко В. П., Курбатова Э. В. Математика: учебное пособие. - Ростов н/Д.: Феникс, 2005.
5. Савин А. П. Энциклопедический словарь юного математика. - М.: Педагогика, 1989.
6. Корн Г., Корн Т. Справочник по математики для научных работников и инженеров. - М.: Наука, 1973.
7. Кирьянов Д. Mathcad 15/MathcadPrime 1.0. - С-Пб.: БХВ-Петербург, 2012.
8. Черняк А., Черняк Ж., Доманова Ю. Высшая математика на базе Mathcad. Общий курс. - С-Пб.: БХВ-Петербург, 2004.
9. Поршнев С., Беленкова И. Численные методы на базе Mathcad. - С-Пб.: БХВ-Петербург, 2012.

Ключевые слова: нелинейные уравнения, прикладная математика, САПР MathCAD, метод Ньютона, шаговый метод, метод дихотомии. .

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

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

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

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

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

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

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

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

Выполнила:

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

группы 06-ИНФ

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

Проверил:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например:

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

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

Сначала напрашивается проверить, наличие рациональных корней. Согласно соответствующей теореме , на это «звание» могут претендовать лишь числа 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) Найдем приближённое значение корня .

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

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

Задача о нахождении решений системы из 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 .