Решение нелинейных уравнений методом Ньютона
Для решения электроэнергетических задач существует несколько моди-фикаций метода. Они позволяют увеличить скорость сходимости итераци-онного процесса и уменьшить время расчета.
Основное достоинство метода – он обладает быстрой сходимостью.
Идея метода состоит в последовательной замене на каждой итерации расчета исходной нелинейной системы уравнений некоторой вспомогатель-ной линейной системой уравнений, решение которой позволяет получить очередное приближение неизвестных, более близкое к искомому решению (линеаризация ).
Рассмотрим нелинейное уравнение в общем виде:
Искомое решение уравнения – точка, в которой кривая пересекает ось абсцисс.
Задаем начальное приближение неиз-вестной х (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), состоящая из уравнений, распадается на две независимые сис-темы размерностью . Каждая из этих систем решается отдельно от другой. Это приводит к сокращению объема вычислений и необходимой памяти ЭВМ.
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
«Приднестровский государственный университет им. Т.Г. Шевченко»
Рыбницкий филиал
Кафедра физики, математики и информатики
Курсовая работа
по дисциплине: «Практикум по решению задач на ЭВМ»
«Метод Ньютона для решения нелинейных уравнений»
Выполнила:
студентка 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), сводится к требованию . В практических расчетах важно выбирать начальное значение как можно ближе к искомому значению, а в программе устанавливать «предохранитель от зацикливания». Недостатком метода является и то, что на каждом шаге необходимо вычислять не только функцию, но и ее производную. Это не всегда удобно. Одна из модификаций метода Ньютона - вычисление производной только на первой итерации: Другой метод модификации – замена производной конечной разностью Тогда Геометрический смысл такого изменения алгоритма Ньютона состоит в том, что от касательной мы приходим к секущей. Метод секущих уступает методу Ньютона в скорости сходимости, но не требует вычисления производной. Заметим, что начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны. Запишем в общем виде алгоритм метода Ньютона. 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. Данная программа создана для работы в текстовом и графическом режиме. Она состоит из модуля 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 – процедура, закрывающая графическую систему. Для тестирования программы возьмем те примеры, которые решали в практической части работы, чтобы сверить результаты и проверить правильность работы программы. 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.
(13)
(14)
(15).
k
x(k)
f(x(k))
f’(x(k))
| x(k+1) - x(k) |
0
0. 565
-4. 387
-9. 982
0. 473
1
0. 092
0. 088
-9. 818
0. 009
2
0. 101
0. 000
-9. 800
0. 000
3
0. 101
k
x(k)
f(x(k))
f’(x(k))
| x(k+1) - x(k) |
0
2
0. 449
0. 361
1. 241
1
-0. 265
0. 881
0. 881
0. 301
2
-0. 021
0. 732
0. 732
0. 029
3
0. 000
0. 716
0. 716
0. 000
4
1. 089
k
x(k)
f(x(k))
f’(x(k))
| x(k+1) - x(k) |
0
1, 000
0, 632
2, 368
0, 267
1
0, 733
0, 057
1, 946
0, 029
2
0, 704
0, 001
1, 903
0, 001
3
0, 703
k
x(k)
f(x(k))
f’(x(k))
| x(k+1) - x(k) |
0
1, 000
-0. 066
0. 462
0. 143
1
1. 161
-0. 007
0. 372
0. 018
2
1. 162
0. 0001.
0. 363
0. 001
3
1. 162
k
x(k)
f(x(k))
f’(x(k))
| x(k+1) - x(k) |
0
1, 000
0, 350
3, 086
0, 114
1
0, 886
0, 013
2, 838
0, 005
2
0, 881
0, 001
2, 828
0, 000
3
0, 881
3.1 Описание программы
3.2 Тестирование программы
Список используемой литературы
Федеральное агентство по образованию
Сочинский государственный университет туризма и курортного дела
Факультет информационных технологий и математики
Кафедра общей математики
Курсовая работа по дисциплине
«Численные методы»
«Метод Ньютона и его модификации решения систем нелинейных уравнений»
Выполнила:
студентка 3 курса
группы 06-ИНФ
Лавренко М.В.
Проверил:
доцент, кандидат
педагогических наук
В связи с развитием новой вычислительной техники инженерная практика наших дней все чаще и чаще встречается с математическими задачами, точное решение которых получить весьма сложно или невозможно. В этих случаях обычно прибегают к тем или иным приближенным вычислениям. Вот почему приближенные и численные методы математического анализа получили за последние годы широкое развитие и приобрели исключительно важное значение.
В данной курсовой работе рассматривается знаменитый метод Ньютона и его модификация решения систем нелинейных уравнений. Решение систем нелинейных уравнений – одна из трудных задач вычислительной математики. Трудность состоит в том, чтобы определить: имеет ли система решение, и, если – да, то сколько. Изучается сходимость основного и упрощенного методов Ньютона и метода, получаемого из метода Ньютона применением итерационного процесса для приближенного обращения матриц Якоби.
А так же коротко описываются: методы ложного положения, метод секущих, метод Стеффенсена, который чаще оказывается лучшим выбором для решения систем нелинейных уравнений нежели метод секущих или метод ложного положения.
Знаменитый метод Ньютона является одним из наиболее эффективных методов решения самых разных нелинейных задач. Расчётную формулу метода можно получить, используя различные подходы. Рассмотрим два из них.
1) Метод касательных.
Выведем расчётную формулу метода для решения нелинейного уравнения
из простых геометрических соображений. Пусть - заданное начальное приближение к корню . В точке с координатами проведём касательную к графику функции и за новое приближение примем абсциссу точки пересечения этой касательной с осью . Аналогично за приближение примем абсциссу точки пересечения с осью касательной, проведённой к графику в точке с координатами . Продолжая этот процесс далее, получим последовательность
приближённой к корню .
Уравнение касательной, проведённой к графику функции
в точке имеет вид: . (1.1)Полагая в равенстве (1.1)
, замечаем, что при выполнении условия абсцисса точки пересечения касательной с осью удовлетворяет равенству: . (1.2)Выражая из него
, получаем расчётную формулу метода Ньютона :
, . (1.3)
Благодаря такой геометрической интерпретации этот метод часто называют методом касательных .
Пусть требуется решить систему уравнений
(1)
- заданные, нелинейные (среди них могут быть и линейные)
вещественнозначные функции п вещественных переменных
. Обозначив ,
, данную систему (2.1) можно записать одним уравнением
(2)относительно векторной функции F векторного аргумента х. Таким образом, исходную задачу можно рассматривать как задачу о нулях нелинейного отображения
В этой постановке она является прямым обобщением основной задачи предыдущей главы - задачи построения методов нахождения нулей одномерных нелинейных отображений. Фактически это та же задача, только в пространствах большей размерности. Поэтому можно как заново строить методы ее решения на основе разработанных выше подходов, так и осуществлять формальный перенос выведенных для скалярного случая расчетных формул. В любом случае следует позаботиться о правомочности тех или иных операций над векторными переменными и векторными функциями, а также о сходимости получаемых таким способом итерационных процессов. Часто теоремы сходимости для этих процессов являются тривиальными обобщениями соответствующих результатов, полученных для методов решения скалярных уравнений. Однако не все результаты и не все методы можно перенести со случая п = 1 на случай п ≥2. Например, здесь уже не будут работать методы дихотомии, поскольку множество векторов не упорядочено. В то же время, переход от n = 1 до n ≥ 2 вносит в задачу нахождения нулей нелинейного отображения свою специфику, учет которой приводит к новым методам и к различным модификациям уже имеющихся. В частности, большая вариативность методов решения нелинейных систем связана с разнообразием способов, которыми можно решать линейные алгебраические задачи, возникающие при пошаговой линеаризации данной нелинейной вектор-функции F ( x ).2) Метод линеаризации.
Метод Ньютона (метод касательных)
Пусть корень уравнения f(x)=0 отделен на отрезке , причем первая и вторая производные f’(x) и f""(x) непрерывны и знакопостоянны при хÎ .
Пусть на некотором шаге уточнения корня получено (выбрано) очередное приближение к корню х n . Тогда предположим, что следующее приближение, полученное с помощью поправки h n , приводит к точному значению корня
x = х n + h n . (1.2.3-6)
Считаяh n малой величиной, представим f(х n + h n) в виде ряда Тейлора, ограничиваясь линейными слагаемыми
f(х n + h n) »f(х n) + h n f’(х n). (1.2.3-7)
Учитывая, что f(x) = f(х n + h n) = 0, получим f(х n) + h n f ’(х n) » 0.
Отсюда h n » - f(х n)/ f’(х n). Подставим значение h n в (1.2.3-6) и вместо точного значения корня x получим очередное приближение
Формула (1.2.3-8) позволяет получить последовательность приближенийх 1 ,х 2 , х 3 …, которая при определенных условиях сходится к точному значению корняx,
то есть 
Геометрическая интерпретация метода Ньютона
состоит в следующем
(рис.1.2.3-6). Примем за начальное приближение x 0 правый конец отрезка b и в соответствующей точке В 0 на графике функции y = f(x) построим касательную. Точка пересечения касательной с осью абсцисс принимается за новое более точное приближение х 1 . Многократное повторение этой процедуры позволяет получить последовательность приближений х 0 , х 1 , х 2 , .
.
., которая стремится к точному значению корня x.
Расчетная формула метода Ньютона (1.2.3-8) может быть получена из геометрического построения. Так в прямоугольном треугольнике х 0 В 0 х 1 катет
х 0 х 1 = х 0 В 0 /tga. Учитывая, что точка В 0 находится на графике функции f(x),
а гипотенуза образована касательной к графику f(x) в точке В 0 , получим
(1.2.3-9)
(1.2.3-10)
Эта формула совпадает с (1.2.3-8) для n-го приближения.
Из рис.1.2.3-6 видно, что выбор в качестве начального приближения точки а может привести к тому, что следующее приближение х 1 окажется вне отрезка , на котором отделен корень x . В этом случае сходимость процесса не гарантирована. В общем случае выбор начального приближения производится в соответствии со следующим правилом: за начальное приближение следует принять такую точку х 0 Î,в которой f(х 0)×f’’(х 0)>0, то есть знаки функции и ее второй производной совпадают.
Условия сходимости метода Ньютона сформулированы в следующей теореме.
Если корень уравнения отделен на отрезке , причем f’(х 0)и f’’(х) отличны от нуля и сохраняют свои знаки при хÎ , то, если выбрать в качестве начального приближения такую точку х 0 Î, что f(х 0).f¢¢(х 0)>0, то корень уравнения f(x)=0может быть вычислен с любой степенью точности.
Оценка погрешности метода Ньютона определяется следующим выражением:
(1.2.3-11)
где -- наименьшее значение 
при 
Наибольшее значение 
при 
Процесс вычислений прекращается, если 
,
где -- заданная точность.
Кроме того, условием достижения заданной точности при уточнении корня методом Ньютона могут служить следующие выражения:
Схема алгоритма метода Ньютона приведена на рис. 1.2.3-7.
Левая часть исходного уравнения f(x) и ее производная f’(x)в алгоритме оформлены в виде отдельных программных модулей.
Рис. 1.2.3-7. Схема алгоритма метода Ньютона
Пример 1.2.3-3.Уточнить методом Ньютона корни уравнения x-ln(x+2) = 0при условии, что корни этого уравнения отделены на отрезках x 1 Î[-1.9;-1.1] и x 2 Î [-0.9;2].
Первая производная f’(x) = 1 – 1/(x+2) сохраняет свой знак на каждом из отрезков:
f’(x)<0 при хÎ [-1.9; -1.1],
f’(x)>0 при хÎ [-0.9; 2].
Вторая производная f"(x) = 1/(x+2) 2 > 0 при любых х.
Таким образом, условия сходимости выполняются. Поскольку f""(x)>0на всей области допустимых значений, то для уточнения корня за начальное приближение x 1 выберем х 0 =-1,9(так какf(-1,9)×f”(-1.9)>0). Получим последовательность приближений:
Продолжая вычисления, получим следующую последовательность первых четырех приближений: -1.9; –1.8552, -1.8421; -1.8414. Значение функции f(x) в точке x=-1.8414 равно f(-1.8414)=-0.00003.
Для уточнения корня x 2 Î[-0.9;2] выберем в качестве начального приближениях 0 =2 (f(2)×f”(2)>0). Исходя из х 0 = 2, получим последовательность приближений: 2.0;1.1817; 1.1462; 1.1461. Значение функции f(x) в точке x=1.1461 равно f(1.1461)= -0.00006.
Метод Ньютона обладает высокой скоростью сходимости, однако на каждом шаге он требует вычисления не только значения функции, но и ее производной.
Метод хорд
Геометрическая интерпретация метода хорд
состоит в следующем
(рис.1.2.3-8).
Проведем отрезок прямой через точки A и B. Очередное приближение x 1 является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой:
Положим y=0и найдем значение х=х 1 (очередное приближение):
Повторим процесс вычислений для получения очередного приближения к корню - х 2 :
В нашем случае (рис.1.2.11) 
и расчетная формула метода хорд будет иметь вид
Эта формула справедлива, когда за неподвижную точку принимается точка b, а в качестве начального приближения выступает точка a.
Рассмотрим другой случай (рис. 1.2.3-9), когда 
.
 |
Уравнение прямой для этого случая имеет вид
Очередное приближение х 1 при y = 0
Тогда рекуррентная формула метода хорд для этого случая имеет вид
Следует отметить, что за неподвижную точку в методе хорд выбирают тот конец отрезка , для которого выполняется условие f (x)∙f¢¢ (x)>0.
Таким образом, если за неподвижную точку приняли точку а, то в качестве начального приближения выступает х 0 = b, и наоборот.
Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х,а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон.
Оценка погрешности метода хорд определяется выражением
(1.2.3-15)
Условие окончания процесса итераций по методу хорд
(1.2.3-16)
В случае, если M 1 <2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.
Пример 1.2.3-4. Уточнить корень уравнения e x – 3x = 0, отделенный на отрезке с точностью 10 -4 .
Проверим условие сходимости:
Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х 0 =1, поскольку f(0)=1>0 и f(0)*f"(0)>0.
2. Метод Ньютона решения систем нелинейных уравнений.
Этот метод обладает гораздо более быстрой сходимостью, чем метод простой итерации. В основе метода Ньютона для системы уравнений (1.1) лежит использование разложения функций
, где 
(2.1)
в ряд Тейлора, причём члены, содержащие вторые и более высокие порядки производных, отбрасываются. Такой подход позволяет решение одной нелинейной системы (1.1) заменить решением ряда линейных систем.
Итак, систему (1.1) будем решать методом Ньютона. В области D выберем любую точку 
и назовём её нулевым приближением к точному решению исходной системы. Теперь функции (2.1) разложим в ряд Тейлора в окрестности точки . Будем иметь
Т.к. левые части (2.2) должны обращаться в ноль согласно (1.1), то и правые части (2.2) тоже должны обращаться в ноль. Поэтому из (2.2) имеем
Все частные производные в (2.3) должны быть вычислены в точке .
(2.3) есть система линейных алгебраических уравнений относительно неизвестных Эту систему можно решить методом Крамера, если её основной определитель будет отличен от нуля и найти величины
Теперь можно уточнить нулевое приближение , построив первое приближение с координатами
т.е.
. (2.6)
Выясним, получено ли приближение (2.6) с достаточной степенью точности. Для этого проверим условие
, 
(2.7)
где 
наперёд заданное малое положительное число (точность, с которой должна быть решена система (1.1)). Если условие (2.7) будет выполнено, то за приближённое решение системы (1.1) выберем (2.6) и закончим вычисления. Если же условие (2.7) выполняться не будет, то выполним следующее действие. В системе (2.3) вместо 
возьмём уточнённые значения
, (2.8)
т.е. выполним следующие действия
. (2.9)
После этого система (2.3) будет системой линейных алгебраических уравнений относительно величин Определив эти величины, следующее второе приближение 
к решению системы (1.1) найдём по формулам
Теперь проверим условие (2.7) 
Если это условие выполняется, то заканчиваем вычисления, приняв за приближённое решение системы (1.1) второе приближение 
. Если же это условие не выполняется, то продолжаем строить следующее приближение, приняв в (2.3) 
Строить приближения нужно до тех пор, пока условие на не будет выполнено.
Рабочие формулы метода Ньютона для решения системы (1.1) можно записать в виде.
Вычислить последовательность
Здесь 
являются решением системы
Сформулируем алгоритм вычислений по формулам (2.11)-(2.13).
1. Выберем нулевое приближение , принадлежащее области D.
2. В системе линейных алгебраических уравнений (2.13) положим 
,а .
3. Решим систему (2.13) и найдём величины 
.
4. В формулах (2.12) положим 
и вычислим компоненты следующего приближения .
5. Проверим условие (2.7) на : (См. алгоритм вычисления максимума нескольких величин.)
6. Если это условие выполняется, то заканчиваем вычисления, выбрав за приближённое решение системы (1.1) приближение . Если же это условие не выполняется, то перейдём к п.7.
7. Положим 
для всех .
8. Выполним п.3, положив 
.
Геометрически этот алгоритм можно записать в виде.
Алгоритм. Вычисления максимума нескольких величин .
Пример . Рассмотрим использование метода Ньютона для решения системы двух уравнений.
Методом Ньютона с точностью до решить следующую систему нелинейных уравнений
, (2.14)
здесь 
. Выберем нулевое приближение 
, принадлежащее области D. Построим систему линейных алгебраических уравнений (2.3). Она будет иметь вид
(2.15)
Обозначим
Решим систему (2.15) относительно неизвестных 
, например методом Крамера. Формулы Крамера запишем в виде
(2.17)
где основной определитель системы (2.15)
(2.18)
а вспомогательные определители системы (2.15) имеют вид
.
Найденные значения подставим в (2.16) и найдём компоненты первого приближения 
к решению системы (2.15).
Проверим условие
, (2.19)
если это условие выполняется, то заканчиваем вычисления, приняв за приближённое решение системы (2.15) первое приближение, т. е. 
. Если условие (2.19) не выполняется, то положим 
, 
и построим новую систему линейных алгебраических уравнений (2.15). Решив её, найдём второе приближение 
. Проверим его на . Если это условие будет выполняться, то за приближённое решение системы (2.15) выберем 
. Если условие на не будет выполняться, положим 
, 
и построим следующую систему (2.15) для нахождения 
и т. д.
Задания
Во всех заданиях требуется:
Составить программу численной реализации метода, согласно предложенному алгоритму.
Получить результаты вычислений.
Проверить полученные результаты.
Задана система двух нелинейных уравнений.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10.
11. 
12. 
13. 
14. 
15. 
.
Глава 3. Численные методы решения систем линейных алгебраических уравнений (СЛАУ).
Цель работы . Знакомство с некоторыми приближёнными методами решения СЛАУ и их численной реализацией на ПК.
Предварительные замечания. Все методы решения СЛАУ обычно разделяют на две большие группы. К первой группе относятся методы, которые принято называть точными. Эти методы позволяют для любых систем найти точные значения неизвестных после конечного числа арифметических операций, каждая из которых выполняется точно.
Ко второй группе относятся все методы, не являющиеся точными. Их называют итерационными, или численными, или приближёнными. Точное решение, при использовании таких методов, получается в результате бесконечного процесса приближений. Привлекательной чертой таких методов является их самоисправляемость и простота реализации на ПК.
Рассмотрим некоторые приближённые методы решения СЛАУ и построим алгоритмы их численной реализации. Приближённое решение СЛАУ будем получать с точностью до , где некоторое очень маленькое положительное число.
1. Метод итерации.
Пусть СЛАУ задана в виде
(1.1)
Эту систему можно записать в матричном виде
, (1.2)
где 
- матрица коэффициентов при неизвестных в системе (1.1), 
- столбец свободных членов, 
- столбец неизвестных системы (1.1).
. (1.3)
Решим систему (1.1) методом итерации. Для этого выполним следующие действия.
Во-первых. Выберем нулевое приближение
(1.4)
к точному решению (1.3) системы (1.1). Компонентами нулевого приближения могут быть любые числа. Но удобнее за компоненты нулевого приближения взять либо нули 
, либо свободные члены системы (1.1) 
Во-вторых. Компоненты нулевого приближения подставим в правую часть системы (1.1) и вычислим
(1.5)
Величины, стоящие слева в (1.5) являются компонентами первого приближения 
Действия, в результате которых получилось первое приближение, называются итерацией.
В-третьих. Проверим нулевое и первое приближения на
(1.6)
Если все условия (1.6) выполняются, то за приближённое решение системы (1.1) выберем, либо , либо всё равно, т.к. они отличаются друг от друга не больше чем на и закончим вычисления. Если хотя бы одно из условий (1.6) не будет выполнено, то перейдём к следующему действию.
В-четвёртых. Выполним следующую итерацию, т.е. в правую часть системы (1.1) подставим компоненты первого приближения и вычислим компоненты второго приближения 
, где
В-пятых. Проверим 
и на , т.е. проверим условие (1.6) для этих приближений. Если все условия (1.6) будут выполнены, то за приближённое решение системы (1.1) выберем, либо , либо всё равно, т.к. они отличаются друг от друга не больше чем на . В противном случае будем строить следующую итерацию, подставив компоненты второго приближения в правую часть системы (1.1).
Итерации нужно строить до тех пор, пока два соседних приближения 
и будут отличаться друг от друга не больше, чем на .
Рабочую формулу метода итерации решения системы (1.1) можно записать в виде
Алгоритм численной реализации формулы (1.7) может быть таким.
Достаточные условия сходимости метода итерации для системы (1.1) имеют вид
1. 
, .
2. 
, 
.
3. 
2. Метод простой итерации.
Пусть система линейных алгебраических уравнений (СЛАУ) задана в виде
(2.1)
Чтобы систему (2.1) решить методом простой итерации, её сначала надо привести к виду
(2.2)
В системе (2.2) 
-ое уравнение представляет собой -ое уравнение системы (2.1), разрешённое относительно –ой неизвестной (
).
Метод решения системы (2.1), состоящий в сведении её к системе (2.2) с последующим решением системы (2.2) методом итерации, называется методом простой итерации для системы (2.1).
Таким образом, рабочие формулы метода простой итерации решения системы (2.1) будут иметь вид
(2.3)
Формулы (2.3) можно записать в виде
Алгоритм численной реализации метода простой итерации для системы (2.1) по формулам (2.4) может быть таким.
Этот алгоритм можно записать геометрически.
Достаточные условия сходимости метода простой итерации для системы (2.1) имеют вид
1. 
, .
2. 
, 
.
3. 
3. Стационарный метод Зейделя.
Метод Зейделя решения СЛАУ отличается от метода итерации тем, что найдя какое-то приближение для -той компоненты, мы сразу же используем его для отыскания следующих 
, 
, …, 
-ой компонент. Такой подход позволяет обеспечить более высокую скорость сходимости метода Зейделя по сравнению с методом итерации.
Пусть СЛАУ задана в виде
(3.1)
Пусть 
- нулевое приближение к точному решению 
системы (3.1). И пусть найдено 
-ое приближение 
. Определим компоненты 
-ого приближения по формулам
(3.2)
Формулы (3.2) можно записать в компактном виде
, 
, 
(3.3)
Алгоритм численной реализации метода Зейделя решения системы (3.1) по формулам (3.3) может быть таким.
1. Выберем , например, 
, 
2. Положим .
3. Для всех вычислим .
4. Для всех проверим условия 
.
5. Если все условия в п.4 будут выполнены, то за приближенное решение системы (3.1) выберем либо , либо и закончим вычисления. Если хотя бы одно условие в п.4 не будет выполнено, перейдем к п.6.
6. Положим и перейдем к п.3.
Этот алгоритм можно записать геометрически.
Достаточное условие сходимости метода Зейделя для системы (3.1) имеет вид 
, .
4. Нестационарный метод Зейделя.
Этот метод решения СЛАУ (3.1) обеспечивает еще более высокую скорость сходимости метода Зейделя.
Пусть каким-либо образом для системы (3.1) найдены компоненты -ого приближения и -ого приближения .
Вычислим вектор поправки
Подсчитаем величины
, (4.2)
Расположим величины 
, в порядке их убывания.
В таком же порядке перепишем уравнения в системе (3.1) и неизвестные в этой системе., : Линейная алгебра и нелинейные ... Руководство для лабораторных работ по ... методические указания для практических работ по для студентов ...
Учебная литература (естественные науки и технические) 2000-2011 цикл опд – 10лет цикл сд – 5 лет
Литература... Естественные науки в целом 1. Астрономия [Текст] : пособие для ... Численные методы : Линейная алгебра и нелинейные ... Руководство для лабораторных работ по ... методические указания для практических работ по дисциплине "Экономика транспорта" для студентов ...
- естественные науки (1)
Учебное пособие... руководство для студентов и преподавателей, предназначенное для использования не только при изучении методов работы ... выработке практических навыков с использованием реальных данных. Методические рекомендации по выполнению зачетной работы по данному...
- естественные науки - физико-математические науки - химические науки - науки о земле (геодезические геофизические геологические и географические науки)
Документ... для студентов естественно - ... работ по дисциплине "Генетика и селекция", посвященных актуальным проблемам этой науки . Систематизирована самостоятельная работа студентов по теоретическому и практическому ... линейного , нелинейного , динамического. Все методы ...
- естественные науки - физико-математические науки - химические науки - науки о земле (геодезические геофизические геологические и географические науки) (7)
Список учебниковОпределитель Еремина в линейной и нелинейной алгебре : линейное и нелинейное программирование: новый метод / Еремин, Михаил... Для студентов и преподавателей геологических специальностей вузов. кх-1 1794549 99. Д3 П 693 Практическое руководство по ...
