Условие сходимости метода ньютона для системы нелинейных уравнений

Численные методы: решение нелинейных уравнений

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

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

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

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

В простейшем случае у нас имеется функция , заданная на отрезке ( a , b ) и принимающая определенные значения.

Каждому значению x из этого отрезка мы можем сопоставить число , это и есть функциональная зависимость, ключевое понятие математики.

Нам нужно найти такое значение при котором такие называются корнями функции

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

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

Простейшим методом нахождения корней уравнения является метод деления пополам или дихотомия.

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

Алгоритм состоит в следующем.

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

Поделим отрезок пополам и введем среднюю точку .

Тогда либо , либо .

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

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

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

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

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

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

Метод Ньютона: теоретические основы

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

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

В уравнении касательной положим и .

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

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

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

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

Упражнение 1. Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

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

Визуализация метода Ньютона

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

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

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

Рассмотрим метод Ньютона на конкретном примере.

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

Уравнение касательной в общем виде имеет представление:

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

Точка пересечения касательной и оси Ox: x₁ =

Рисунок 2. Результат первой итерации

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

Точка пересечения касательной и оси Ox: x₂ = .

Рисунок 3. Вторая итерация метода Ньютона

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

В3 = ()

Рисунок 4. Третий шаг метода касательных

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

= 1.5.

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

=

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

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

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

using namespace std;

float f(double x) //возвращает значение функции f(x) = x^2-2

float df(float x) //возвращает значение производной

float d2f(float x) // значение второй производной

int _tmain(int argc, _TCHAR* argv[])

int exit = 0, i=0;//переменные для выхода и цикла

double x0,xn;// вычисляемые приближения для корня

double a, b, eps;// границы отрезка и необходимая точность

cin>>a>>b; // вводим границы отрезка, на котором будем искать корень

cin>>eps; // вводим нужную точность вычислений

if (a > b) // если пользователь перепутал границы отрезка, меняем их местами

if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня

cout 0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // считаем первое приближение

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

xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона

> while (exit!=1); // пока пользователь не ввел exit = 1

Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5.

Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку.

Рис. 4. Решение ошибки компиляции проекта

Мы будем искать корни у функции f(x) = x2-2.

Сначала проверим работу приложения на «неправильных» входных данных. На отрезке [3; 5] нет корней, наша программа должна выдать сообщение об ошибке.

У нас появилось окно приложения:

Рис. 5. Ввод входных данных

Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет.

Рис. 6. Ошибка «На этом отрезке корней нет!»

Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0».

Теперь проверим работу приложения на корректных входных данных. Введем отрезок [0; 2] и точность 0.0001.

Рис. 7. Вычисление корня с необходимой точностью

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

Чтобы выйти из приложения, введем «Exit?» => 1.

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

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

/

Итерационный процесс имеет вид:

где .

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

Порядок сходимости метода секущих ниже, чем у метода касательных и равен в случае однократного корня .

Эта замечательная величина называется золотым сечением:

Убедимся в этом, считая для удобства, что .

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

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

После подстановки имеем: и

Для сходимости необходимо, чтобы было положительным, поэтому .

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

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

Как только начнется рост, вычисления прекращают и последнюю итерацию не используют.

Такая процедура определения момента окончания итераций называется приемом Гарвика.

Метод парабол

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

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

В форме Ньютона она имеет вид:

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

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

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

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

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

Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки.

Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).

По теореме Банаха существует и единственна неподвижная точка

Она может быть найдена как предел простой итерационной процедуры

где начальное приближение — произвольная точка промежутка .

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

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

Условие существенно, ибо если, например, на [0,1] , то неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины . Чем меньше , тем быстрее сходимость.

Рассмотрим уравнение: .

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

Однако можно в качестве можно взять, например, функцию . Соответствующая итерационная процедура имеет вид: .

Эти итерации сходятся к неподвижной точке для любого начального приближения :

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

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

т.е. такой итерационный процесс всегда сходится.

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

Здесь нетрудно убедиться, что при существует окрестность корня, в которой .

то если корень кратности , то в его окрестности и, следовательно,.

Если — простой корень, то сходимость метода касательных квадратичная (то есть порядок сходимости равен 2).

Поскольку , то

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

Нахождение всех корней уравнения

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

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

Для поиска других корней используется метод удаления корней.

Пусть — корень функции , рассмотрим функцию. Точка будет являться корнем функции на единицу меньшей кратности, чем, при этом все остальные корни у функций и совпадают с учетом кратности.

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

Повторяя указанную процедуру, можно найти все корни с учетом кратности.

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

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

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

Курсовая работа: Метод Ньютона для решения нелинейных уравнений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f(a)*f(b) 0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 — о квадратичной, m=3 — о кубической сходимостях.

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

; (5,6)

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

(7)

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

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

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

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

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

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

x* О [a,c] , если f(c)Ч f(b) 0 ;

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

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

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

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

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

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

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

(12)

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

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

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

.

3. Если | x (k+1) — x (k) | (k+1) . Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.

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

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

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

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

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

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.

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нелинейные системы и уравнения

В более общем случае мы имеем не одно уравнение (1), а систему нелинейных уравнений $$ \begin \tag <2>f_i(x_1, x_2, \ldots, x_n) = 0, \quad i = 1, 2, \ldots n. \end $$ Обозначим через \( \mathbf = (x_1, x_2, \ldots, x_n) \) вектор неизвестных и определим вектор-функцию \( \mathbf(\mathbf) = (f_1(\mathbf), f_2(\mathbf), \ldots, f_n(\mathbf)) \). Тогда система (2) записывается в виде $$ \begin \tag <3>\mathbf(\mathbf) = 0. \end $$ Частным случаем (3) является уравнение (1) (\( n = 1 \)). Второй пример (3) — система линейных алгебраических уравнений, когда \( \mathbf (\mathbf) = A \mathbf — \mathbf \).

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

Решение нелинейных уравнений

При итерационном решении уравнений (1), (3) задается некоторое начальное приближение, достаточно близкое к искомому решению \( x^* \). В одношаговых итерационных методах новое приближение \( x_ \) определяется по предыдущему приближению \( x_k \). Говорят, что итерационный метод сходится с линейной скоростью, если \( x_ — x^* = O(x_k — x^*) \) и итерационный метод имеет квадратичную сходимость, если \( x_ — x^* = O(x_k — x^*)^2 \).

В итерационном методе Ньютона (методе касательных) для нового приближения имеем $$ \begin \tag <4>x_ = x_k + \frac, \quad k = 0, 1, \ldots, \end $$

Вычисления по (4) проводятся до тех пор, пока \( f(x_k) \) не станет близким к нулю. Более точно, до тех пор, пока \( |f_(x_k)| > \varepsilon \), где \( \varepsilon \) — малая величина.

Простейшая реализация метода Ньютона может выглядеть следующим образом:

Чтобы найти корень уравнения \( x^2 = 9 \) необходимо реализовать функции

Данная функция хорошо работает для приведенного примера. Однако, в общем случае могут возникать некоторые ошибки, которые нужно отлавливать. Например: пусть нужно решить уравнение \( \tanh(x) = 0 \), точное решение которого \( x = 0 \). Если \( |x_0| \leq 1.08 \), то метод сходится за шесть итераций.

Теперь зададим \( x_0 \) близким к \( 1.09 \). Возникнет переполнение

Возникнет деление на ноль, так как для \( x_7 = -126055892892.66042 \) значение \( \tanh(x_7) \) при машинном округлении равно \( 1.0 \) и поэтому \( f^\prime(x_7) = 1 — \tanh(x_7)^2 \) становится равной нулю в знаменателе.

Проблема заключается в том, что при таком начальном приближении метод Ньютона расходится.

Еще один недостаток функции naive_Newton заключается в том, что функция f(x) вызывается в два раза больше, чем необходимо.

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

1. обрабатывать деление на ноль
2. задавать максимальное число итераций в случае расходимости метода
3. убрать лишний вызов функции f(x)

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

При реализации метода Ньютона нужно знать аналитическое выражение для производной \( f^\prime(x) \). Python содержит пакет SymPy, который можно использовать для создания функции dfdx . Для нашей задачи это можно реализовать следующим образом:

Решение нелинейных систем

Идея метода Ньютона для приближенного решения системы (2) заключается в следующем: имея некоторое приближение \( \pmb^ <(k)>\), мы находим следующее приближение \( \pmb^ <(k+1)>\), аппроксимируя \( \pmb(\pmb^<(k+1)>) \) линейным оператором и решая систему линейных алгебраических уравнений. Аппроксимируем нелинейную задачу \( \pmb(\pmb^<(k+1)>) = 0 \) линейной $$ \begin \tag <5>\pmb(\pmb^<(k)>) + \pmb(\pmb^<(k)>)(\pmb^ <(k+1)>— \pmb^<(k)>) = 0, \end $$ где \( \pmb(\pmb^<(k)>) \) — матрица Якоби (якобиан): $$ \pmb<\nabla F>(\pmb^<(k)>) = \begin \frac<\partial f_1(\pmb^<(k)>)> <\partial x_1>& \frac<\partial f_1(\pmb^<(k)>)> <\partial x_2>& \ldots & \frac<\partial f_1(\pmb^<(k)>)> <\partial x_n>\\ \frac<\partial f_2(\pmb^<(k)>)> <\partial x_1>& \frac<\partial f_2(\pmb^<(k)>)> <\partial x_2>& \ldots & \frac<\partial f_2(\pmb^<(k)>)> <\partial x_n>\\ \vdots & \vdots & \ldots & \vdots \\ \frac<\partial f_n(\pmb^<(k)>)> <\partial x_1>& \frac<\partial f_n(\pmb^<(k)>)> <\partial x_2>& \ldots & \frac<\partial f_n(\pmb^<(k)>)> <\partial x_n>\\ \end $$ Уравнение (5) является линейной системой с матрицей коэффициентов \( \pmb \) и вектором правой части \( -\pmb(\pmb^<(k)>) \). Систему можно переписать в виде $$ \pmb(\pmb^<(k)>)\pmb <\delta>= — \pmb(\pmb^<(k)>), $$ где \( \pmb <\delta>= \pmb^ <(k+1)>— \pmb^ <(k)>\).

Таким образом, \( k \)-я итерация метода Ньютона состоит из двух стадий:

1. Решается система линейных уравнений (СЛАУ) \( \pmb(\pmb^<(k)>)\pmb <\delta>= -\pmb(\pmb^<(k)>) \) относительно \( \pmb <\delta>\).

2. Находится значение вектора на следующей итерации \( \pmb^ <(k+1)>= \pmb^ <(k)>+ \pmb <\delta>\).

Для решения СЛАУ можно использовать приближенные методы. Можно также использовать метод Гаусса. Пакет numpy содержит модуль linalg , основанный на известной библиотеке LAPACK, в которой реализованы методы линейной алгебры. Инструкция x = numpy.linalg.solve(A, b) решает систему \( Ax = b \) методом Гаусса, реализованным в библиотеке LAPACK.

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

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