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

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

2014-06-18

123.78 KB

27 чел.


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

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


КУРСОВАЯ РАБОТА

(пояснительная записка)

по курсу

Вычислительные методы                                                                         

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

Ньютона 

 

 

 


Оглавление

[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. Теоретический раздел

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

f(x)=0 (1)

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

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

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

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

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

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

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

, (3)

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

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

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

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

, (4)

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

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

;  (5,6)

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

(7)

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

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

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

1)Метод итераций. При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x0 и точность ε. Первое приближение решения x1 находим из выражения x1=f(x0), второе - x2=f(x1) и т.д. В общем случае i+1

приближение найдем по формуле xi+1 =f(xi). Указанную процедуру

повторяем пока |f(xi)|>ε. Условие сходимости метода итераций |f'(x)|<1.

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

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

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

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

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

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) < 0 .

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

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

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

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

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

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

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

.

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

 (8)

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

(9)

y                                                        

                                                          x

Рис.1                                                                                                              

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

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

var y:real;

begin

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

if abs(f(x)) > eps

then X_Newt:=X_Newt(y,eps)

else X_Newt:=y

end;

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

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

x=g(x) (10)

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

xk+1=g(xk) (11)

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

Всегда ли описанный вычислительный процесс приводит к искомому

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

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

(a)                                                                  (б)

Рис. 3.

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

(12)

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

функции: g’(x)=1+q*f’(x). Наибольшую сходимость получим при g’(x)=0, тогда q= - 1/f’(x) и формула (11) переходит в формулу Ньютона (9).

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

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

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

(13)

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

(14)

Тогда  (15)

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

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

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

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

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

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

.

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

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

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

Пример:

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

x2 - e-x = 0.

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

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

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

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

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

3. Разработка программного продукта

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) – процедура, которая устанавливает текущий цвет фона, используя палитру, в данном случае – это светло-синий цвет.

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

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

у1) в точку с координатами (х2, у2);

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

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

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

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

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

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

x2 - e-x = 0.

Тест:

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

Введите а = -1

Введите b=1

[a, b] = [-1, 1]

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

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

                                                              

 

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

x = 0.703.

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

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

3.3 Блок-схема алгоритма

Блок схема алгоритма метода Ньютона приведена рисунке.

Заключение

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

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

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

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

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

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

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

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

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

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

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

PAGE  21



 

Другие похожие работы, которые могут вас заинтересовать.
6217. Методы нахождения корней системы нелинейных уравнений 284.94 KB
  Методы нахождения корней системы нелинейных уравнений. Для системы из 2 уравнений это можно сделать графически но для систем высоких порядков удовлетворительных методов отделения корней не существует. Проблема решения системы 1 возникает при решении многих прикладных задач например поиска безусловного экстремума функций многих переменных с помощью необходимых условий...
6396. Виды нелинейных дифференциальных уравнений 1-го порядка 163.25 KB
  Дифференциальное уравнение уравнение связывающее значение некоторой неизвестной функции в некоторой точке и значение её производных различных порядков в той же точке. Дифференциальное уравнение содержит в своей записи неизвестную функцию её производные и независимые переменные; однако не любое уравнение содержащее производные неизвестной функции является дифференциальным уравнением. Нелинейное дифференциальное уравнение дифференциальное уравнение обыкновенное или с частными производными в которое по крайней мере одна...
19450. Численные методы решения нелинейных уравнений 156.56 KB
  Видим что обе части не являются алгебраическими и содержат тригонометрические формулы значит это трансцендентное уравнение для решения которого не существует формул для отыскания корней. Построим график для того чтобы примерно определить промежутки содержащие корни см. Для этого реализуем метод половинного деления. Для того чтобы использовать эту функцию напишем скрипт который будет выводить первые пять корней отмечать их на графике а также использовать встроенную функцию для проверки решения и вычислять резонансные частоты стержня.
22. Интерполирование функций полинома методом Ньютона 215.52 KB
  Освоить методы алгоритмизации и программирования двух форм представления интерполяционного полинома: полиномов Лагранжа и Ньютона с равномерным расположением узлов интерполирования.3 Исследовать зависимость ошибки интерполирования функции от количества и расположения узлов интерполирования Лагранжа и Ньютона. ВЫВОД В результате выполнения данной работы были изучены методы алгоритмизации и программирования интерполяционного полинома Ньютона с равномерным расположением узлов интерполирования и исследована зависимость ошибки интерполирования....
841. Теоретическая информатика. Решение систем линейных уравнений методом Крамара 90.58 KB
  Информация ее виды и свойства Единицы количества информации: вероятностный и объемный подходы. Теоретическая информатика математическая дисциплина использующая методы математики для построения и изучения моделей обработки передачи и использования информации. Но как правило эти модели наполнены конкретным содержанием связанным со спецификой информации того объекта который нас интересует. В них разрабатываются методы позволяющие использовать достижения логики для анализа процессов переработки информации с помощью...
9173. Механика и методология Ньютона 17.2 KB
  Одним из первых, кто задумался о сущности движения, был Аристотель. Аристотель определяет движение как изменение положения тела в пространстве. Пространство, по Аристотелю, целиком заполнено материей, неким подобием эфира или прозрачной, как воздух субстанцией. Пустоты в природе нет («природа боится пустоты»).
2252. Метод Ньютона минимизации функции многих переменных 47.99 KB
  В этих методах для определения направления убывания функции использовалась лишь линейная часть разложения функции в ряд Тэйлора. Если же минимизируемая функция дважды непрерывно дифференцируема то возможно применение методов минимизации второго порядка которые используют квадратичную часть разложения этой функции в ряд Тэйлора. Разложение функции по формуле Тейлора в окрестности точки можно представить в виде Отсюда видно что поведение функции с точностью до величин порядка описывается квадратичной функцией 7.
11851. Исследование устойчивости относительно части переменных в критическом случае пары чисто мнимых и одного нулевого корней 4.31 MB
  К настоящему времени теория является общепризнанной во всем мире и находит широкое применение в различных областях науки и техники. До работ Ляпунова в исследованиях устойчивости ограничивались рассмотрением лишь первого приближения. Он сумел четко разделить при каких случаях она решается а при каких – нет. Он доказал основные общие теоремы а результаты были применены для изучения устойчивости космических аппаратов проведено систематическое исследование вопроса.
17499. Анализ спектра и измерение нелинейных искажений 273.17 KB
  Спектральный способ основан на представлении (аппроксимации) сигнала в виде суммы гармонических составляющих разных, обычно кратных друг другу частот. Процессы в электрических цепях получаются тем сложнее, чем более сложной является форма сигналов. В этих случаях часто становится эффективным и полезным спектральное представление сигналов.
13460. ИССЛЕДОВАНИЕ НЕЛИНЕЙНЫХ СИСТЕМ МЕТОДАМИ ЛЯПУНОВА 397.97 KB
  Любая динамическая система способна совершать множество движений, вызываемых теми или иными причинами. Среди этого множества существуют движения, которые система должна совершать в соответствии со своим назначением. Это движение Ляпунов предложил называть невозмущенным движением
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.