Численные методы для решения одного уравнения
Дифференциальным уравнением первого порядка называется уравнение вида F(x,y,у’)=0 или у’=f(x,y). Функция y(x), при подстановке которой уравнение обращается в тождество, называется решением дифференциального уравнения.
Рассмотрим несколько численных методов решения дифференциальных уравнений первого порядка. Описание численных методов приводится для уравнения в виде у’=f(x,y).
Рассмотрим два варианта вывода расчетных формул
Лекция «Численные методы решения уравнений»
учебно-методический материал
Лекция по разделу «Численные методы».
Рассматриваются следующие методы решения алгебраических и трансцендентных уравнений:
1) метод дихотомии (метод деления отрезка пополам),
3) метод касательных,
4) метод итераций.
Скачать:
| Вложение | Размер |
|---|---|
| численные методы решения уравнений | 87 КБ |
Предварительный просмотр:
Тема 12.2.Приближенное решение алгебраических и трансцендентных уравнений.
Задача о нахождении приближенных значений действительных корней уравнения f(x)=0 предусматривает предварительное отделение корня , т.е. установления промежутка, в котором других корней данного уравнения нет.
Будем предполагать, что функция f(x) в промежутке [a; b] непрерывна вместе со своими производными f’(x) и f’’(x) , значения f(а) и f(b) функции на концах промежутка имеют разные знаки, т.е. f(а) ∙ f(b) , и обе производные f’(x) и f’’(x) сохраняют знак во всем промежутке [a; b].
Т.к. действительными корнями уравнения f(x)=0 являются абсциссы точек пересечения кривой y=f(x) с осью ОХ , то отделение корня можно произвести графически.
Иногда полезно уравнение f(x)=0 записать в виде . Действительными корнями исходного уравнения служат абсциссы точек пересечения графиков функций .
Мы рассмотрим 4 численных решения уравнений.
1. Метод дихотомии (метод деления отрезка пополам).
Этот метод можно использовать когда нам предположительно или точно известны границы отрезка, содержащего корень и на этих границах f(x) принимает значения разных знаков, тогда по теореме о достаточных условиях существования корня на заданном отрезке существует хотя бы один корень.
y 
- Делим отрезок [a; b] пополам.
- Определяем, на границах какой из частей первоначального интервала функция f(x) меняет знак.
- Полученный интервал снова делим на две части и т.д.
Такой процесс продолжаем до тех пор, пока не перестанут изменяться сохраняемые в ответе десятичные знаки.
Пусть требуется вычислить действительный корень уравнения f(x)=0 , изолированный на отрезке [a;b]. Рассмотрим график функции у= f(x) . Пусть f(а) и f(в) >0. Точки графика А[a;f(a)] и В[b;f(b)] соединим хордой .За приближенное значение искомого корня примем абсциссу х 1 точки пересечения хорды АВ с осью Ох .
Это приближенное значение находится по формуле , где x 1 ∈ (a;b)
Пусть, например, f(x 1 ) тогда за новой (более узкий) промежуток изоляции корня принять [x 1 ,b].
Соединив точки А 1 [x 1 ;f(x 1 )] и В[b;f(b)] , получим в точке пересечения хорды с осью Ох второе приближение x 2 , которое вычислим по формуле: и т.д.
Последовательность чисел a 1 , x 1 , x 2 ,… стремится к искомому корню уравнения f(x)=0 .Вычисление приближенных значений корней уравнения следует вести до тех пор, пока не перестанут изменятся те десятичные знаки, которые мы хотим сохранить в ответе (т.е.пока не будет достигнута заданная степень точности)
Если Х-точный корень уравнения f(x)=0 , изолированный на отрезке [а,в] , а ξ- приближенное значение корня ,найденное методом хорд ,то оценка погрешности этого приближенного значения такова:
- Метод касательных (Метод Ньютона)
Пусть действительный корень уравнения f(x)=0 изолирован на отрезке [а,в] . Будем предполагать, что все ограничения, сформулированные выше относительно f(x) , сохраняют силу и в этом случае. Выделяем на отрезке [а,в] такое число x 0 , при котором f(x 0 ) имеет тот же знак, что и f’’(x 0 ) т.е. f(x 0 ) f’’(x 0 )>0 (в частности , за x 0 может быть принят тот из концов отрезка [а,в] , в котором соблюдено это условие). Проведем в точке Мо[x 0 , f(x 0 )] касательную к кривой y=f(x) .
y= f(x)
За приближенное значение корня примем абсциссу точки пересечения этой касательной с осью Ох . Это приближенное значение корня находится по формуле: .
Применив этот прием вторично в точке M 1 [x 1 ; f(x 1 )] , найдем и т.д.
Полученная т.об. последовательность x 0 , x 1 , x 2 ,… имеет своим пределом искомый корень.
Для оценки погрешности приближенного значения корня, найденного, методом Ньютона, может быть .использовано неравенство:
4. Метод итераций.
Если данное уравнение приведено к виду , где всюду на отрезке [а,в] , на котором исходное уравнение имеет единственный корень, то исходя из некоторого начального .значения x 0 , принадлежащего отрезку [а,в] , можно построить такую последовательность: …
Пределом этой последовательности является единственный корень уравнения f(x)=0 на отрезке [а,в]. Погрешность приближенного значения x n корня Х , найденного методом итерации, оценивается неравенством.
y y=x Численные методы решения систем нелинейных уравненийВведениеМногие прикладные задачи приводят к необходимости нахождения общего решения системы нелинейных уравнений. Общего аналитического решения системы нелинейных уравнений не найдено. Существуют лишь численные методы. Следует отметить интересный факт о том, что любая система уравнений над действительными числами может быть представлена одним равносильным уравнением, если взять все уравнения в форме Для численного решения применяются итерационные методы последовательных приближений (простой итерации) и метод Ньютона в различных модификациях. Итерационные процессы естественным образом обобщаются на случай системы нелинейных уравнений вида: Обозначим через Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].
Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами. С этим трудно не согласится хотя бы потому, что в том числе и разнообразие модулей подняло Python на вершину популярности. Однако, существуют случаи, когда даже при поверхностном рассмотрении использование прямых известных методов без применения специальных функций библиотеки SciPy тоже дают неплохие результаты. Иными словами, новое- это хорошо забытое старое. Так, в публикации [2], на основании проведенных вычислительных экспериментов, доказано, что библиотечная функция newton_krylov, предназначенная для решения больших систем нелинейных уравнений, имеет в два раза меньшее быстродействие, чем алгоритм TSLS+WD Целью настоящей публикации является сравнение по числу итераций, быстродействию, а главное, по результату решения модельной задачи в виде системы из ста нелинейных алгебраических уравнений при помощи библиотечной функции scipy.optimize.root и методом Ньютона, реализованного средствами библиотеки NumPy. Возможности решателя scipy.optimize.root для численного решения систем алгебраических нелинейных уравненийБиблиотечная функция scipy.optimize.root выбрана в качестве базы сравнения, потому что имеет обширную библиотеку методов, пригодных для сравнительного анализа. scipy.optimize.root(fun, x0, args=(), method=’hybr’, jac=None, tol=None,callback=None, ptions=None) method: Методы решения систем нелинейных уравненийПриведенный далее материал действительно можно прочитать в литературе, например в [4], но я уважаю своего читателя и для его удобства приведу вывод метода по возможности в сокращенном виде. Те, кто не любит формулы, этот раздел пропускают. В методе Ньютона новое приближение для решения системы уравнений (2) определяется из решения системы линейных уравнений: Определим матрицу Якоби: Запишем(3) в виде: Многие одношаговые методы для приближенного решения (2) по аналогии с двухслойными итерационными методами для решения систем линейных алгебраических уравнений можно записать в виде: где При использовании записи (6) метод Ньютона (5) соответствует выбору:
Система линейных уравнений (5) для нахождения нового приближения При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений. Нелинейный метод Зейделя применительно к решению (2) дает: В этом случае каждую компоненту нового приближения из решения нелинейного уравнения, можно получить на основе метода простой итерации и метода Ньютона в различных модификациях. Тем самым снова приходим к двухступенчатому итерационному методу, в котором внешние итерации проводятся в соответствии с методом Зейделя, а внутренние — с методом Ньютона. Основные вычислительные сложности применения метода Ньютона для приближенного решения систем нелинейных уравнений связаны с необходимостью решения линейной системы уравнений с матрицей Якоби на каждой итерации, причем от итерации к итерации эта матрица меняется. В модифицированном методе Ньютона матрица Якоби обращается только один раз: Выбор модельной функцииТакой выбор не является простой задачей, поскольку при увеличении числа уравнений в системе в соответствии с ростом числа переменных результат решения не должен меняться, поскольку в противном случае невозможно отследить правильность решения системы уравнений при сравнении двух методов. Привожу следующее решение для модельной функции: Функция f создаёт систему из n нелинейных уравнений, решение которой не зависит от числа уравнений и для каждой из n переменных равно единице. Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью библиотечной функции optimize.root для разных методов отыскания корнейТолько один из методов, приведенных в документации [3] прошёл тестирование по результату решения модельной функции, это метод ‘krylov’. Решение для n=100: Solution: Вывод: С увеличением числа уравнений вдвое заметно появление ошибок в решении. При дальнейшем увеличении n решение становится не приемлемым, что возможно из-за автоматической адаптации к шагу, эта же причина резкого падения быстродействия. Но это только моё предположение. Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью программы написанной на Python 3 с учётом соотношений (1)-(8) для отыскания корней по модифицированному методу НьютонаРешение для n=100: Solution: Решение для n=200: Solution: Чтобы убедиться в том, что программа действительно решает систему, перепишем модельную функцию для ухода от корня со значением 1 в виде: Получим: Вывод: Программа работает и при изменении модельной функции. Теперь вернёмся к начальной модельной функции и проверим более широкий диапазон для n, например в 2 и 500. источники: http://nsportal.ru/npo-spo/estestvennye-nauki/library/2019/05/07/lektsiya-chislennye-metody-resheniya-uravneniy http://habr.com/ru/post/419453/ |
, возвести их в квадрат и сложить.
(1)
вектор неизвестных и определим вектор-функцию 
Тогда система (1) записывается в виде уравнения:
(2)
(3)
(4)
(5)
(6)
— итерационные параметры, a 
— квадратная матрица n х n, имеющая обратную.
может решаться итерационно. В этом случае мы имеем двухступенчатый итерационный процесс с внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основе итерационного метода Зейделя
(7)
(8)