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

Обновлено: 02.07.2024

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

ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

1п. Общий вид нелинейного уравнения

Нелинейные уравнения могут быть двух видов:

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

Значение х₀ при котором существует равенство f(x₀)=0 называется корнем уравнения.

В общем случае для произвольной F(x) не существует аналитических формул определения корней уравнения. Поэтому большое значение имеют методы, которые позволяют определить значение корня с заданной точностью. Процесс отыскания корней делиться на два этапа:

Отделение корней, т.е. определение отрезка содержащего один корень.

Уточнение корня с заданной точностью.

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

Второй этап, уточнение корня выполняется различными итерационными методами, суть которых в том, что строится числовая последовательность x_i сходящихся к корню x₀

Выходом из итерационного процесса являются условия:

рассмотрим наиболее употребляемые на практике методы: дихотомии, итерации и касательных.

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

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

Данный отрезок [a,b] делится пополам, т.е. определяется x₀=(a+b)/2, получается два отрезка [a,x₀] и [x₀,b], далее выполняется проверка знака на концах, полученных отрезков для отрезка, имеющего условия f(a)*f(x₀)?0 или f(x₀)*f(b)?0 снова проводится деление пополам координатой х, снова выделение нового отрезка и так продолжается процесс до тех пор пока ?x_n-x_n_-1.

3п. Метод итерации.

Дана непрерывная функция f(x), которая содержит единственный корень на отрезке [a,b], где b>a. Определить корень с точностью ?.

Заменим уравнение (1) равносильным уравнением x=?(x) (2). Выберем грубое, приближенное значение x₀ , принадлежащее[a,b], подставим его в правую часть уравнения (2), получим:

x₁= ?(x₀) (3) , далее подставим х₁ в правую часть уравнения (3) получим:

Проделаем данный процесс n раз получим x_n=?(x_n_-1)

Если эта последовательность является сходящейся т.е. существует предел

x * =lim x_n , то данный алгоритм позволяет определить искомый корень.

Выражение (5) запишем как x * = ?(x * ) (6)

Выражение (6) является решением выражения (2), теперь необходимо рассмотреть в каких случаях последовательность х₁…х_n является сходящейся.

4 п. Метод касательных (Ньютона).

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

Выбираем грубое приближение корня х₀ (либо точку a, либо b)

Наити значение функции точке х₀ и провести касательную до пересечения с осью абсцисс, получим значение х₁

5п. Задание для РГР

Вычислить корень уравнения

На отрезке [2,3] с точностью ?=10 -4 методами половинного деления, итерации, касательных.

6 п. Сравнение методов

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

Наиболее универсальным является метод половинного деления, он гарантирует определение корня с заданной точностью для любой функции f(x), которая меняет знак на [a,b]. Метод итерации и метод Ньютона предъявляют к функциям более жесткие требования, но они обладают высокой скоростью сходимости.

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

Программа по методам половинного деления, итерации и метода Ньютона.

a = 2: b = 3: E = .0001

DEF FNZ (l) = 3 * SIN(SQR(l)) + .35 * l - 3.8

F1 = FNZ(a): F2 = FNZ(b)

IF F1 * F2 > 0 THEN PRINT "УТОЧНИТЬ КОРНИ": END

IF ABS((-3 * COS(SQR(x))) / (.7 * SQR(x))) > 1 THEN PRINT "НЕ СХОДИТСЯ"

DEF FNF (K) = -(3 * SIN(SQR(x)) - 3.8) / .35

DEF FND (N) = (3 * COS(SQR(N)) / (2 * SQR(N))) + .35 _

IF F * (-4.285 * (-SQR(x0) * SIN(SQR(x)) - COS(SQR(x))) / (2 * x * SQR(x))) E THEN 1 ?

Выполнил: студент (ЦДО)

№спец. 230102 (АСОИУ)

Проверил: Обухова Л.Г.

г. Набережные Челны – 2010 г.

Введение	3
1. ОСНОВНЫЕ ЭТАПЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ	4
2. МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ)	7
Заключение	11
Список использованной литературы	12

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

1 ОСНОВНЫЕ ЭТАПЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

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

где - нелинейная функция вида:

- нелинейная алгебраическая функция (полином или многочлен);

- тригонометрическая, логарифмическая, показательная функция;

- комбинирование этих функций, например .

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

На практике не всегда удается найти точное решение. В этом случае решения уравнения (1.1) находят с применением приближенных (численных) методов.

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

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

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

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

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

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

2) если функция непрерывна на отрезке , выполняется условие вида и производная сохраняет знак на , то на отрезке имеется единственный корень.

3) если функция является многочленом n -й степени и на концах отрезка принимает значения разных знаков, то на имеется нечетное количество корней. Если на концах отрезка функция меняет знак, то уравнение (1.1) либо не имеет корней на , либо имеет четное количество корней.

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

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

2 МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ).

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

По формуле Тейлора получим

Внося эту правку в формулу (2.1), получим рабочую формулу метода Ньютона вида:

Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой касательной, проведенной в некоторой точке этой кривой.

Для определенности положим и . Выберем начальное приближение , для которого . Проведем касательную к кривой в точке . За первое приближение берем точку пересечения касательной с осью . На кривой определим точку и проведем касательную к кривой в этой точке. Найдем следующее приближение и так далее (рис. 2.1).

Составим уравнение касательной в точке :

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

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

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

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

Доказательство.

Пусть для определенности при (остальные случаи рассматриваются аналогично).

Из неравенства следует, что , т.е. .

Докажем, что все приближения расположены правее , т.е. , а значит .

Доказательство проведем методом индукции:

б) предположим, что ;

Точное решение уравнения (1.1) можно представить в виде

Применяя формулу Тейлора, получим:

Так как по условию теоремы , то последнее слагаемое в соотношении (2.3) положительное, следовательно,

Отсюда, в силу того, что , получим:

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

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

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

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

Следует заметить, что чем больше числовое значение в окрестности корня , тем меньше правка . Поэтому методом Ньютона удобно пользоваться, когда в окрестности искомого корня график функции имеет большую крутизну (т.е. , тогда ). Если кривая вблизи точки пересечения с осью почти горизонтальна (т.е. , тогда ), то применять метод Ньютона для решения уравнения (1.1) не рекомендуется.

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

Если выполнено условие (2.5), то итерационный процесс, заданный формулой (2.2), будет сходиться при произвольном выборе начального приближения .

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

Достоинства метода Ньютона:

1) обладает достаточно большой скоростью сходимости, близкой к квадратичной;

2) достаточно простое получение итерационной формулы.

Недостатки метода Ньютона:

1) сходится не при любом выборе начального приближения;

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

2. Красильников В.В. Математичемкие методы в экономике. Набережные Челны, 1999, 475 с.

3. Горбунов Д.А., Комиссарова Е.М. Вычислительная математика: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2008. 148 с.

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

Рубрика	Математика
Вид	реферат
Язык	русский
Дата добавления	31.10.2013
Размер файла	353,5 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

Введение

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

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

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

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

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

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

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

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

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

- f(a) - f(b) 0; f (x) 0; f (x) 0

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

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

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

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

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

- вычисляем , пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности - до выполнения неравенства | x_i-x_i-1| * ), при которых все функции f_i равны 0.

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

1 этап - отделение решений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из графика видим, что система имеет одно решение, заключенное в области D: 0 ( k ) решения системы нелинейных уравнений x_i * . Введем в рассмотрение поправку x_i как разницу между решением и его приближением:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6) Уточняется решение

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

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

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

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

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

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

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

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

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

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

Метод Ньютона для решения нелинейных уравнений ( реферат , курсовая , диплом , контрольная )

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

Рыбницкий филиал Кафедра физики, математики и информатики

Курсовая работа

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

330 й группы специальности: «Информатика

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

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

2008 год
Оглавление
Введение 3
Цели и задачи. 3
I. Теоретический раздел. 5
- 1.1 Обзор существующих методов решения нелинейных уравнений. 7
- 1.2 Алгоритм метода Ньютона. 9
- 3.1 Описание программы. 23
- 3.2 Тестирование программы. 24
Внедрение ЭВМ во все сферы человеческой деятельности требует от специалистов разного профиля овладения навыками использования вычислительной техники. Повышается уровень подготовки студентов вузов, которые уже с первых курсов приобщаются к использованию ЭВМ и простейших численных методов, не говоря уже о том, при что выполнении курсовых и дипломных проектов применение вычислительной техники становится нормой в подавляющем большинстве вузов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

then X_Newt:=X_Newt (y, eps)

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

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

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

Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (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 (0) так, чтобы выполнилось условие

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

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

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

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

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

Пример 1

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

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

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

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

F'(x)=2x cos x 2 — 2x sin x 2 — 10.

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

F''(x)=2cos x 2 — 4 x 2 sin x 2 — 2sin x 2 — 4 x 2 cos x 2 = cos x 2 (2−4 x 2 ) — sin x 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,

Выполнил: студент (ЦДО)

№спец. 230102 (АСОИУ)

Проверил: Обухова Л.Г.

г. Набережные Челны – 2010 г.

1. ОСНОВНЫЕ ЭТАПЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

2. МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ)

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

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

1 ОСНОВНЫЕ ЭТАПЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

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

где - нелинейная функция вида:

- нелинейная алгебраическая функция (полином или многочлен);

- тригонометрическая, логарифмическая, показательная функция;

- комбинирование этих функций, например .

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

На практике не всегда удается найти точное решение. В этом случае решения уравнения (1.1) находят с применением приближенных (численных) методов.

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

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

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

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

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

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

2) если функция непрерывна на отрезке , выполняется условие вида и производная сохраняет знак на , то на отрезке имеется единственный корень.

3) если функция является многочленом n -й степени и на концах отрезка принимает значения разных знаков, то на имеется нечетное количество корней. Если на концах отрезка функция меняет знак, то уравнение (1.1) либо не имеет корней на , либо имеет четное количество корней.

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

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

2 МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ).

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

По формуле Тейлора получим

Внося эту правку в формулу (2.1), получим рабочую формулу метода Ньютона вида:

Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой касательной, проведенной в некоторой точке этой кривой.

Для определенности положим и . Выберем начальное приближение , для которого . Проведем касательную к кривой в точке . За первое приближение берем точку пересечения касательной с осью . На кривой определим точку и проведем касательную к кривой в этой точке. Найдем следующее приближение и так далее (рис. 2.1).

Составим уравнение касательной в точке :

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

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

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

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

Пусть для определенности при (остальные случаи рассматриваются аналогично).

Из неравенства следует, что , т.е. .

Докажем, что все приближения расположены правее , т.е. , а значит .

Доказательство проведем методом индукции:

б) предположим, что ;

Точное решение уравнения (1.1) можно представить в виде

Применяя формулу Тейлора, получим:

Так как по условию теоремы , то последнее слагаемое в соотношении (2.3) положительное, следовательно,

Отсюда, в силу того, что , получим:

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

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

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

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

Следует заметить, что чем больше числовое значение в окрестности корня , тем меньше правка . Поэтому методом Ньютона удобно пользоваться, когда в окрестности искомого корня график функции имеет большую крутизну (т.е. , тогда ). Если кривая вблизи точки пересечения с осью почти горизонтальна (т.е. , тогда ), то применять метод Ньютона для решения уравнения (1.1) не рекомендуется.

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

Если выполнено условие (2.5), то итерационный процесс, заданный формулой (2.2), будет сходиться при произвольном выборе начального приближения .

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

Достоинства метода Ньютона:

1) обладает достаточно большой скоростью сходимости, близкой к квадратичной;

2) достаточно простое получение итерационной формулы.

Недостатки метода Ньютона:

1) сходится не при любом выборе начального приближения;

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

2. Красильников В.В. Математичемкие методы в экономике. Набережные Челны, 1999, 475 с.

3. Горбунов Д.А., Комиссарова Е.М. Вычислительная математика: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2008. 148 с.

Похожие страницы:

Нелинейные уравнения и способы их решения

. в которой был изложен метод для решения линейных систем, известный как метод исключения. В 40-х . корня уравнения с точностью ε по методу Ньютона условием окончания итераций может служить: | x(k+1) - x(k) | ≤ ε Решение нелинейных уравнений методом простой .

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

. : . (1.10) 2. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. 2.1. ОПИСАНИЕ МЕТОДА. Обобщим метод Ньютона, изложенный в пункте 1 для решения одного нелинейного уравнения, на решение систем нелинейных уравнений. При .

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

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

Итерациональные методы решения нелинейных уравнений

. 3. Итерационные методы решения систем нелинейных уравнений. §3.1. Метод простых итераций для решения систем нелинейных уравнений. 36 §3.2. Метод Ньютона для решения систем нелинейных уравнений. 40 Глава 4. Итерационные методы решения систем линейных .

Численные методы. Лабораторный практикум

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

Читайте также:

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

Метод Ньютона для решения нелинейных уравнений ( реферат , курсовая , диплом , контрольная )

Похожие страницы:

Нелинейные уравнения и способы их решения

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

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

Итерациональные методы решения нелинейных уравнений

Численные методы. Лабораторный практикум