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

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

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

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

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

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

студентка 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.

Решение уравнений методом ньютона курсовая

Читинский Государственный Университет

Факультет экономики и информатики

Кафедра прикладной информатики и математики

по дисциплине: Численные методы

на тему: Метод Ньютона (метод касательных). Решение систем нелинейных алгебраических уравнений

Выполнила: ст. гр. ПИ-07-1

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

1.1 Геометрическая интерпретация метода Ньютона

1.2 Алгоритм решения задач с помощью метода Ньютона

1.3 Примеры решения уравнений с помощью метода Ньютона

2. Решение систем нелинейных алгебраических уравнений

2.1 Метод итераций

2.1.1 Пример решения системы уравнений с помощью метода итераций

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

2.2.1 Пример решения системы уравнений с помощью метода Ньютона

2.3 Метод спуска

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

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

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

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

.1 Геометрическая интерпретация метода Ньютона

Этот метод применяется, если уравнение f(x) = 0 имеет корень x Î [a;b], и выполняются условия:

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

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

) f ¢ (x) ¹ 0 при 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 сначала удобно выбирать один из концов отрезка.

Пусть нам дана некоторая функция f(x) = 0 на отрезке [a,b]. Возможно 4 случая:

— f(a)-f(b) ¢ (x) > 0; f ² (x) > 0

f(a)-f(b) ¢ (x) > 0; f ² (x)

f(a)-f(b) > 0; f ¢ (x) ² (x) > 0

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

Пусть нам дана возрастающая функция y = f(x), непрерывная на отрезке [a;b], и имеющая f ¢ (x) > 0 и f ² (x) > 0. Уравнение касательной имеет вид: y-y0= f ¢ (x 0 )?(x-x 0 ). В качестве точки x0 выбираем точку B(b; f(b)). Проводим касательную к функции y = f(x) в точке B, и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x1, получаем точку b 1 . Снова проводим касательную к функции y = f(x) в точке b 1 , и обозначаем точку пересечения касательной и оси Ox точкой x2. Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку b 2 .

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

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

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

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e — до выполнения неравенства | xi-xi-1| ¢ (x) и f ² (x), причем f ¢ (x) ¹ 0 при x Î [a;b], f ¢ (x) и f ² (x) должны сохранять знак на отрезке [a;b]

выбираем один из концов отрезка [a,b] за x 0 , исходя из того, что должно выполняться следующее условие f(x 0 )?f ² (x 0 )>0.

— вычисляем , пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e — до выполнения неравенства | xi-xi-1| 1,30,253137-1,470291,5-0,26435-0,12004

Так как, при x = 1,5, то за x0, берем x = 1,5.

Так как , то на данном шаге можно остановится.

) Решить уравнение с .

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

Построив графики функций и , определяем, что у решаемого уравнения имеется только один корень, который находится в интервале 0.4 — отделение решений.

2 этап — уточнение всех или только нужных решений.

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

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

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

Достаточным признаком монотонности функции f(x) на отрезке [ a;b ] является сохранение знака производной функции.

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

Наличие графика исходной функции дает непосредственное представление о количестве и расположении нулей функции, что позволяет определить промежутки, внутри которых содержится только один корень. Если построение графика функции у = f(x) вызывает затруднение, часто оказывается удобным преобразовать данное уравнение к эквивалентному виду f 1 (x)=f 2 (x) и построить графики функций у = f 1 (x) и у = f 2 (x) Абсциссы точек пересечения этих графиков будут соответствовать значениям корней решаемого уравнения.

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

Для систем с большим числом неизвестных (n ³ 3) удовлетворительных общих методов определения области существования решения нет. Поэтому при решении СНУ эта область обычно определяется при анализе решаемой задачи, например, исходя из физического смысла неизвестных.

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

Отделение решений позволяет:

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

) Проанализировать возможность применения выбранного метода решения СНУ в каждой области.

) Выбрать начальное приближение решения x 0 из области его существования, так что x 0 Î D.

При отсутствии информации об области существования решения СНУ выбор начального приближения x 0 проводиться методом проб и ошибок.

Методы уточнения решений СНУ.

Уточнение интересующего решения до требуемой точности ? производится итерационными методами.

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

.1 Метод итераций

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

и построении итерационной последовательности X(k+1) = ?(X(k)), где k=1,2,3,… — номер итерации, которая при k?? сходится к точному решению.

В развернутом виде формула итерационного процесса (выражение для вычисления очередного k-го приближения решения) имеет вид:

Условие окончания расчета

где ? — заданная точность решения;

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

Таким образом, для уточнения решения СНУ методом простых итераций нужно найти такое эквивалентное преобразование в X=?(X), чтобы в области существования решения выполнялись условия сходимости.

.1.1 Пример решения системы уравнений с помощью метода итераций

Решить систему нелинейных уравнений с точностью до 0,003

Дана система нелинейных уравнений:

Перепишем данную систему в виде:

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

Из графика видим, что система имеет одно решение, заключенное в области D: 0 00,15-2-0,45-0,435-0,4161-0,138710,16128-2,035-0,4387-0,4248-0,4477-0,149220,15077-2,0248-0,4492-0,4343-0,4385-0,146230,15382-2,0343-0,4462-0,4315-0,4471-0,14940,15098-2,0315-0,449-0,4341-0,4446-0,148250,1518-2,0341-0,4482-0,4333-0,4469-0,14960,15104-2,0333-0,449-0,434-0,4462-0,148770,15126-2,034-0,4487-0,4338-0,4468-0,148980,15105-2,0338-0,4489-0,434-0,4467-0,1489

Так как . где , то

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

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

Пусть известно приближение xi(k) решения системы нелинейных уравнений xi*. Введем в рассмотрение поправку Dxi как разницу между решением и его приближением:

Подставим полученное выражение для xi* в исходную систему.

Неизвестными в этой системе нелинейных уравнений являются поправки Dxi. Для определения Dxi нужно решить эту систему. Но решить эту задачу так же сложно, как и исходную. Однако эту систему можно линеаризовать, и, решив ее, получить приближенные значения поправок Dxi для данного приближения, т.е. Dxi(k). Эти поправки не позволяют сразу получить точное решение , но дают возможность приблизиться к решению, — получить новое приближение решения

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

Полученная система имеет вид:

Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения x i (k) . Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n — метод исключения Гаусса.

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

Можно использовать и среднее значение модулей поправок:

В матричной форме систему можно записать как:

где: , — матрица Якоби (производных),

W(X(k)) — матрица Якоби, вычисленная для очередного приближения.

F(X(k)) — вектор-функция, вычисленная для очередного приближения.

Выразим вектор поправок ?X(k) из :

где W-1 — матрица, обратная матрице Якоби.

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

Достаточные условия сходимости для общего случая имеют очень сложный вид, и на практике проверяются редко. Нужно отметить, что метод сходится очень быстро (за 3 — 5 итераций), если det|W| ¹ 0 и начальное приближение X (0) выбрано близким к решению (отличаются не более чем на 10%).

Алгоритм решения СНУ методом Ньютона состоит в следующем:

1) Задается размерность системы n, требуемая точность ?, начальное приближенное решение .

) Вычисляются элементы матрицы Якоби

) Вычисляется обратная матрица .

) Вычисляется вектор функция , , .

) Вычисляются вектор поправок

) Оценивается достигнутая точность

) Проверяется условие завершения итерационного процесса .

Если оно не соблюдается, алгоритм выполняется снова с пункта 2.

Для уменьшения количества арифметических действий Рафсон предложил не вычислять обратную матрицу W-1, а вычислять поправки как решение СЛУ: , данный метод получил название метод Ньютона-Рафсона.

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

.2.1 Пример решения системы уравнений с помощью метода Ньютона

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

Отделение корней производим графически.

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

Значения для x можно брать исходя из следующих условий:

из первого уравнения -1 -0.76

За начальное приближение примем x 0 =0.4; y 0 =-0.75.

Имеем следующие системы:

Найдем элементы матрицы Якоби , где , и значения функций в x0=0.4; y0=-0.75:

Все вычисления производим в таблице.

nxn0.8xn22xn-ynsin(2xn-yn)F(xn,yn) detWdetW1?xyn1.5yn2cos(2xn-yn)G(xn,yn) detW2?y00,4000,12801,550,999780,11978-1,15841-0,020792,61970,27010,1031-0,7500,843750,02079-0,028250,64000-2,250000,043940,0167710,50310,202491,739430,98581-0,01791-1,535680,167843,2429-0,0379-0,0117-0,73320,80644-0,16780,008930,80496-2,19969-0,0007-0,000220,49140,193191,716280,98944-0,00026-1,489940,144973,164-0,0006-0,0002-0,73340,80692-0,14490,000110,78627-2,20034-0,00005-0,00001

Так как ? Теги: Метод Ньютона (метод касательных). Решение систем нелинейных алгебраических уравнений Курсовая работа (теория) Математика

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

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

Дата добавления: 2014-06-18

Размер файла: 123.78 KB

Работу скачали: 36 чел.

Поделитесь работой в социальных сетях

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

на тему Вычисление корней нелинейных уравнений методом

[1] Цели и задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Теоретический раздел

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

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

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

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

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

знака постоянства первой производной , то можно утверждать о существовании единственного корня на заданном отрезке.

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

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

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

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

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

где С>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)|

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 (в к )

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

4). Метод хорд . Идея метода состоит в том, что на отрезке [a,b] строится хорда стягивающая концы дуги графика функции 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,c] или [c,b] в зависимости от знаков значений функции в точках a,b,c

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

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

Если f'(x) не меняет знак на [a,b], то обозначая 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)

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

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

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

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

Далее получим следующее приближение в точке , проводя касательную из точки () до пересечения с осью абсцисс:

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

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

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

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

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

Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (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)=1+q*f’(x). Наибольшую сходимость получим при g’(x)=0, тогда q= — 1/f’(x) и формула (11) переходит в формулу Ньютона (9).

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

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

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

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

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

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

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

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

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

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

2. Практический раздел

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

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

Вычисления производить с точностью ε = 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.

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