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

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

Введение

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

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

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

(1)

Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

(2)

Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].

Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

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

Так, в публикации [2], на основании проведенных вычислительных экспериментов, доказано, что библиотечная функция newton_krylov, предназначенная для решения больших систем нелинейных уравнений, имеет в два раза меньшее быстродействие, чем алгоритм TSLS+WD
(two-step least squares), реализованный средствами библиотеки NumPy.

Целью настоящей публикации является сравнение по числу итераций, быстродействию, а главное, по результату решения модельной задачи в виде системы из ста нелинейных алгебраических уравнений при помощи библиотечной функции 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)
fun — Векторная функция для поиска корня.
x0 –Начальные условия поиска корней

method:
hybr -используется модификация Пауэлл гибридный метод;
lm – решает системы нелинейных уравнений методом наименьших квадратов.
Как следует из документации [3] методы broyden1, broyden2, anderson, linearmixing, diagbroyden, excitingmixing, krylov являются точными методами Ньютона. Остальные параметры являются «не обязательными» и с ними можно ознакомится в документации.

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

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

В методе Ньютона новое приближение для решения системы уравнений (2) определяется из решения системы линейных уравнений:

(3)

Определим матрицу Якоби:

(4)

Запишем(3) в виде:

(5)

Многие одношаговые методы для приближенного решения (2) по аналогии с двухслойными итерационными методами для решения систем линейных алгебраических уравнений можно записать в виде:

(6)

где — итерационные параметры, a — квадратная матрица n х n, имеющая обратную.

При использовании записи (6) метод Ньютона (5) соответствует выбору:

Система линейных уравнений (5) для нахождения нового приближения может решаться итерационно. В этом случае мы имеем двухступенчатый итерационный процесс с внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основе итерационного метода Зейделя

При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений. Нелинейный метод Зейделя применительно к решению (2) дает:

(7)

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

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

(8)

Выбор модельной функции

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

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

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

Только один из методов, приведенных в документации [3] прошёл тестирование по результату решения модельной функции, это метод ‘krylov’.

Решение для n=100:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1.]
Krylov method iteration = 4219
Optimize root time 7.239 seconds:

Вывод: С увеличением числа уравнений вдвое заметно появление ошибок в решении. При дальнейшем увеличении n решение становится не приемлемым, что возможно из-за автоматической адаптации к шагу, эта же причина резкого падения быстродействия. Но это только моё предположение.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью программы написанной на Python 3 с учётом соотношений (1)-(8) для отыскания корней по модифицированному методу Ньютона

Решение для n=100:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1.]
Newton iteration = 13
Newton method time 0.496 seconds

Решение для n=200:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1.]
Newton iteration = 14
Newton method time 1.869 seconds

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

Получим:
Solution:
[ 0.96472166 0.87777036 0.48175823 -0.26190496 -0.63693762 0.49232062
-1.31649896 0.6865098 0.89609091 0.98509235]
Newton iteration = 16
Newton method time 0.046 seconds

Вывод: Программа работает и при изменении модельной функции.

Теперь вернёмся к начальной модельной функции и проверим более широкий диапазон для n, например в 2 и 500.
n=2
Solution:
[1. 1.]
Newton iteration = 6
Newton method time 0.048 seconds
n=500

Методы решения систем нелинейных уравнений
статья по алгебре (9 класс) по теме

В работе рассмотрены раличные методы решения систем неленейных уравнений: 1) метод подстановки; 2) метод независимого решения одного из уравнений; 3) сведение системы к объединению более простых систем; 4) метод алгебраического сложения; 5) метод умножения уравнений;6) метод деления уравнений; 7) метод введения новых переменных ;8) применение теоремы Виета; 9) симметричные системы;10) «Граничные задачи»;11) графический метод.

Скачать:

Предварительный просмотр:

Методы решения систем нелинейных уравнений.

( Работа педагога дополнительного образования Куца Федора Ивановича, МБОУ ДОД ДДТ г, Зверево РО, объединение «Школа решения нестандартных задач по математике»)

1) Метод подстановки.

a) Метод прямой подстановки.

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

Решить систему уравнений

Корнями уравнения у 2 +2у –3 = 0 являются у 1 = 1, у 2 = — 3.

b) Комбинирование с другими методами.

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

Решить систему уравнений

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

2) Метод независимого решения одного из уравнений.

Идея метода . Если в системе содержится уравнение, в котором находятся взаимно обратные выражения, то вводится новая переменная и относительно её решается уравнение. Затем система распадается на несколько более простых систем.

Решить систему уравнений

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

Сделав замену t = , где t ≠ 0, получаем t + = , 4t 2 — 17t + 4 = 0.

Откуда t 1 = 4, t 2 = .

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

Корнями уравнения 4у 2 – 15у – 4 = 0 являются у 1 = 4, у 2 = — .

Корнями уравнения 4х 2 + 15х – 4 = 0 являются х 1 = — 4, х 2 = .

3)Сведение системы к объединению более простых систем.

a) Разложение на множители способом вынесения общего множителя.

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

Решить систему уравнений

Разложим на множители второе уравнение системы.

Решим первую систему (1) или (2)

Решим вторую систему

b) Разложение на множители через решение однородного уравнения .

Идея метода. Если одно из уравнений представляет собой однородное уравнение ( , то решив его относительно одной из переменных, раскладываем на множители, например: a(x-x 1 )(x-x 2 ) и, учитывая равенство выражения нулю, переходим к решению более простых систем.

Решить систему уравнений

Решим уравнение относительно х.

D = (-5у) 2 – 4 ∙1 ∙ 25у 2 – 16у 2 = 9у 2 .

х 1,2 = = . х 1 = 4у, х 2 = у.

Система принимает вид: Откуда:

Решим первую систему

D = (-2) 2 – 4 ∙3 ∙ 4 + 96 = 100.

у 1,2 = = . у 1 = 2, у 2 = — .

Решим вторую систему

D = (-1) 2 – 4 ∙24 ∙ 1 + 384 = 385.

у 1,2 = у 1 = , у 2 = .

c) Использование однородности.

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

Решить систему уравнений

Умножим первое уравнение на (-3), второе — на 5 и сложим.

Решим уравнение относительно х.

D = (3у) 2 – 4 ∙(-4) ∙ 9у 2 +112у 2 = 121у 2 .

х 1,2 = = . х 1 = у, х 2 = — у.

Система принимает вид: Откуда 1) или 2)

Решим первую систему

Решим вторую систему

4) Метод алгебраического сложения.

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

Решить систему уравнений

Уравняем модули коэффициентов при переменной величине у, для этого первое уравнение умножим на 3, а второе на 2.

Прибавив к первому уравнению второе, получаем

Решим первое уравнение системы ,

Так как 15 + 14 — 29 = 0, то х 1 = 1, х 2 = — .

5) Метод умножения уравнений.

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

Решить систему уравнений

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

; Возведя обе части уравнения в квадрат, имеем:

(у – 3)( + 2) 2 = у 2 ; (у – 3)(у + 4 + 4) = у 2 ;

у 2 + 4у + 4у – 3у — 12 -12 = у 2 ; 4у + 4у – 3у — 12 — 12 = 0.

Пусть = t, тогда 4t 3 + t 2 -12t -12 = 0.

Применяя следствие из теоремы о корнях многочлена, имеем t 1 = 2.

Р(2) = 4∙2 3 + 2 2 — 12∙2 – 12 = 32 + 4 — 24 — 12 = 0.

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

4t 3 + t 2 -12t -12 = (t – 2) (at 2 + bt + c).

4t 3 +t 2 -12t -12 = at 3 + bt 2 + ct — 2at 2 -2bt — 2c.

4t 3 + t 2 — 12t -12 = at 3 + (b – 2a) t 2 + (c -2b) t — 2c.

Получаем уравнение 4t 2 + 9t + 6 = 0, которое не имеет корней, так как D = 9 2 — 4∙4∙6 = -15

Возвращаясь к переменной у, имеем = 2, откуда у = 4.

6) Метод деления уравнений.

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

Решить систему уравнений

Разделим первое уравнение на второе

7) Метод введения новых переменных.

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

Решить систему уравнений

Введем новые переменные: х + у = u, = v.

Возвращаясь к старым переменным, имеем:

Решаем первую систему.

Находим решение второй системы.

8) Применение теоремы Виета .

Идея метода. Если система составлена так, одно из уравнений представлено в виде суммы, а второе — в виде произведения некоторых чисел, которые являются корнями некоторого квадратного уравнения, то применяя теорему Виета составляем квадратное уравнение и решаем его.

Решить систему уравнений

х, у корни уравнения: а 2 — 5а + 4 = 0. Откуда а 1 = 1, а 2 = 4.

Следовательно(1) или (2)

9) Симметричные системы.

Идея метода. (Многочлен от двух переменных х и у называется симметричным, если он не изменяется при замене х на у и у на х.). Свойство симметричных систем: если пара чисел (х 0 ;у 0 ) является решением системы, то и пара (у 0 ;х 0 ) также является ее решением.

Для решения симметричных систем применяется подстановка: х + у = а; ху = в.

При решении симметричных систем используются следующие преобразования:

х 2 + у 2 = (х + у) 2 – 2ху = а 2 – 2в; х 3 + у 3 = (х + у)(х 2 – ху + у 2 ) = а(а 2 -3в);

х 2 у + ху 2 = ху (х + у) = ав; (х +1)∙(у +1) = ху +х +у+1 =а + в +1;

Решить систему уравнений

Сделаем замену: х + у = а; ху = в; х 2 + у 2 = (х + у) 2 – 2ху = а 2 – 2в.

Решим уравнение . а 1 = 2, а 2 = 3.

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

10) «Граничные задачи».

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

Решить систему уравнений

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

Исходя из вида уравнений, попытаемся найти множество значений функции , которая встречается и в первом, и во втором уравнении системы. Так как х 2 + 4 ≥ 4, то из первого уравнения следует, что ≥ 4, а значит, ≥ 16. С другой стороны, исходя из области определения функции , получаем, что 16 – ≥ 0, откуда ≤ 16.Таким Образом,16 ≤ ≤ 16, т. е. = 16. Подставим полученное значение в систему:

11) Графический метод.

Идея метода . Строят графики функций в одной системе координат и находят координаты точек их пересечения.

Решить систему уравнений

1) Переписав первое уравнение систем в виде у = х 2 , приходим к выводу: графиком уравнения является парабола.

2) Переписав второе уравнение систем в виде у = , приходим к выводу: графиком уравнения является гипербола.

3) Парабола и гипербола пересекаются в точке А. Точка пересечения только одна, поскольку правая ветвь параболы служит графиком возрастающей функции, а правая ветвь гиперболы — убывающей. Судя по построенной геометрической модели точка А имеет координаты (1;2). Проверка показывает, что пара (1;2) является решением обоих уравнений системы.

Решите системы уравнений.

1.Алгебра. ЕГЭ: шаг за шагом / А.А.Черняк, Ж.А.Черняк.- Волгоград: Учитель,2012.

2.Методы решения задач по математике: Пособие для поступающих в НПИ. Ч1 / Ред. журн. « Изв. вузов. Электромеханика». Новочеркасск,1993.

3.Алгебра, 9 класс, В 2 ч. Ч.1. Учебник для учащихся общеобразовательных учреждений/ А.Г. Мордкович, П.В. Семенов. – 12-е изд., стер. – М. : Мнемозина, 2010.

По теме: методические разработки, презентации и конспекты

Методы решения систем уравнений

Урок по алгебре в 9 классе по теме: «Методы решения систем уравнений» учителя математики Шевченко ТИИспользованные программы:1C Математический конструктор 3.0Диск Алгебра. Электронное сопр.

Урок алгебры в 9классе по теме «методы решения систем уравнений»

Подготовка к ГИА по теме «Решение систем уравнений».

Методическая разработка урока алгебры в 7 классе «Различные способы решения систем линейных уравнений» способы решения систем уравнений

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

Материалы к практическому занятию по математике для студентов специальности Экономика и бухгалтерский учет по теме «Графический метод решения систем линейных уравнений»

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

Методы решения систем логических уравнений

Методы решения систем логических уравнений при подготовке к ЕГЭ (задание В15).

Презентация Методы решения систем линейных уравнений (метод подстановки)

Системы уравнений с двумя переменными. Графический метод решения систем двух линейных уравнений с двумя переменными

Урок объяснения нового материала по учебнику «Алгебра, 7 класс» А.Г. Мерзляк, параграф 26. Презентация составлена для объяснения новой темы в Zoom при дистанционном обучении.

Дипломная работа: Сравнительный анализ численных методов

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

По дисциплине: ”Математическое обеспечение САПР»

Тема: «Сравнительный анализ численных методов»

1. Постановка задачи

2. Методы решения нелинейных уравнений

2.1 Общие сведения

2.2 Метод касательных (метод Ньютона)

2.2.1 Общие сведения

2.2.2 Решение нелинейного уравнения методом касательных

2.3.1 Общие сведения

2.3.2 Решение нелинейного уравнения методом хорд

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

2.5.1 Общие сведения

2.5.2 Решение нелинейного уравнения методом простых итераций

2.6 Программа для решения нелинейных уравнений

3. Решение нелинейных уравнений методом интерполирования

3.2 Многочлен Лагранжа

3.3 Интерполяция сплайнами

3.4 Использование интерполяции на практике

3.4.1 Интерполяция с помощью многочлена Лагранжа

3.4.2 Обратная интерполяция

3.4.3 Интерполяция сплайнами

3.5 Программа для использования интерполяции

4. Итерационные методы решения систем линейных алгебраических уравнений

4.1 Общие сведения

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

4.2.1 Описание метода

4.2.2 Решение СЛАУ методом простых итераций

4.2.3 Программа для решения СЛАУ методом простых итераций

4.3 Метод Зейделя

4.3.1 Описание метода

4.3.2 Решение СЛАУ методом Зейделя

4.3.3 Программа дл решения СЛАУ методом Зейделя

4.4 Сравнительный анализ

5. Сравнительный анализ различных методов численного дифференцирования и интегрирования

5.1 Методы численного дифференцирования

5.1.1 Описание метода

5.1.2 Нахождение производной

5.2 Методы численного интегрирования

5.2.1 Общие сведения

5.2.2 Нахождение определенного интеграла

5.3.1 Решение ОДУ методом Эйлера

5.3.2 Решение ОДУ методом Рунге-Кутты

6.Численные методы решения обыкновенных дифференциальных уравнений

6.1 Общие сведения

6.2 Метод Эйлера

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

Введение

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

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

В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLABи т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.

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

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

1. Постановка задачи

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

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

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

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

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

Сравнить результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации.

Провести сравнительный анализ различных методов численного дифференцирования и интегрирования.

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

2. Методы решения нелинейных уравнений

2.1 Общие сведения

Рассмотрим уравнение вида f (x) =0, (2.1), где f (x) — любая нелинейная функция.

Корнем уравнения ( 2.1) называется значение , при котором. Способы приближенного решения, т.е. алгоритм решения, предполагает определение x * c некоторой наперед заданной точностью.

Для нахождения корней уравнения (2.1) различают следующие два этапа.

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

Уточнение корней заключается в применении некоторого итерационного метода, в результате которого корень уравнения (2.1) может быть получен с любой наперед заданной точностью ε. При этом, останавливая процесс на какой-либо конечной итерации, необходимо оценить погрешность по сравнению с точным корнем, который неизвестен. Выбранный метод позволяет построить последовательность х₁ , х₂ , х₃ , …, х_k , … приближений к корню. Итерационный процесс состоит в последовательном уточнении начального приближения х0. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х1, х2, х3, …, хk, … Если эти значения с ростом k стремятся к истинному значению корня , то итерационный процесс сходится.

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

2.2 Метод касательных (метод Ньютона)

2.2.1 Общие сведения

Метод Ньютона, называемый также методом касательных, состоит в следующем. Рассмотрим в точке x₀ касательную к кривой y=f (x), задаваемую уравнением

За начальное приближение x₀ принимается один из концов отрезка [a, b], где значение функции имеет такой же знак, что и 2-я производная. Функция f (x) должна удовлетворять на отрезке [a, b] следующим условиям:

1) существование производных 1-го и 2-го порядков;

2) f ’ (x) 0;

3) производные 1-го и 2-го порядков знакопостоянны на отрезке [a, b].

Положим y=0, находим точку x₁ пересечения касательной с осью абсцисс:

Построив касательную в точке x_{1 (} рисунок 2.1), получаем по аналогичной формуле точку x₂ пересечения этой касательной с осью x и т.д. Формула для n-го приближения имеет вид:

Рисунок 2.1 — Метод касательных

В этом методе на n-й итерации проводится касательная к кривой y =f (x) при х=xn-1 и ищется точка пересечения касательной с точкой абсцисс. При этом необязательно задавать отрезок [a,b], содержащий корень уравнения, а достаточно лишь найти некоторое начальное приближение корня х.

Итерационный процесс останавливают при выполнении условия ; где ε — заданная точность.

2.2.2 Решение нелинейного уравнения методом касательных

1. Дано уравнение tg (0.36*x +0.4) =x 2 . Решить его методом касательных с точностью решения=0,001.

Для нахождения корня исследуем функцию

.

График функции представлен на рисунке 2.2

Рисунок 2.2 — График исследуемой функции

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

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.3

Рисунок 2.3 — График функции на выбранном отрезке

Проверяем существование корня на отрезке по условию

x>0.001

x>0.001

,

x 3 -0,2x 2 +0,4x-1,4=0.

Решить его методом касательных с точностью решения=0,001.

Для нахождения корня исследуем функцию

.

График функции представлен на рисунке 2.5

Рисунок 2.5 — График исследуемой функции

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

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.6

Рисунок 2.6 — График функции на выбранном отрезке

Проверяем существование корня на отрезке по условию

-3,066375

Экстремумов на выбранном отрезке нет.

Находим первую производную функции:

;

В точке a первая и вторая производные равны:

,

В точке bпервая и вторая производные равны:

,

Выбираем тот конец отрезка, значение функции в котором совпадает со знаком 2-ой производной.

x₀ = 1,5 2.125*6.55=13,91875,

x>0.001

x>0.001

x>0.001

x 2 .

Решить его методом хорд с точностью решения=0,001.

Как в предыдущем методе для нахождения корня исследуем функцию

.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.9

Рисунок 2.9 — График функции на выбранном отрезке

По данным из п.2.2.2 за x₀ выбираем тот конец отрезка, который совпадает со знаком 2-ой производной. А за x₁ второй конец отрезка.

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x 3 -0,2x 2 +0,4x-1,4=0. Решить его методом хорд с точностью решения=0,001.

Как в предыдущем методе для нахождения корня исследуем функцию

.

График функции представлен на рисунке 2.5

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.11

Рисунок 2.11 — График функции на выбранном отрезке.

По данным из п.2.2.2 за x₀ выбираем тот конец отрезка, который совпадает со знаком 2-ой производной и удовлетворяет условию . А за x₁ второй конец отрезка.

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x 0 вычисления следует вести до тех пор, пока не окажется выполненным неравенство

Если величина , то можно использовать более простой критерий окончания итераций:

2.5.2 Решение нелинейного уравнения методом простых итераций

1. Дано уравнение tg (0.36*x +0.4) =x 2 . Решить его методом простых итераций с точностью решения=0,001. Как в предыдущих методах для нахождения корня исследуем функцию

.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.14.

Рисунок 2.14 — График функции на выбранном отрезке

Приведем уравнение к виду x=x- af (x), где итерационная функция  (x) =x- af (x), a — итерационный параметр.

Максимальное и минимальное значения производной достигаются на концах отрезка:

Применяем формулу x=x — af (x) =f (x):

2. Дано уравнение x 3 -0,2x 2 +0,4x-1,4=0. Решить его методом методом простых итераций с точностью решения=0,001.

Для нахождения корня исследуем функцию .

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.15.

Рисунок 2.15 — График функции на выбранном отрезке.

Найдем корень с помощью встроенной функции root :

Приводим уравнение к виду x= f (x), где

Проверим условие сходимости:

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

Применяем формулу x=  (x):

2.6 Программа для решения нелинейных уравнений

На рисунках 2.16, 2.17 представлены программы для решения нелинейных уравнений методами хорд и касательных.

Пользователь вводит необходимые данные и при нажатии кнопки «Решить» выводится результат.

Листинги программ представлены в приложениях А, Б.

Рисунок 2.16 — Программа для решения методом касательных

Рисунок 2.17 — Программа для решения методом хорд

3. Решение нелинейных уравнений методом интерполирования

3.1 Интерполяция

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

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

Допустим, в n+1 точке заданы значения x₀ ,x₁ ,…x_n и соответствующие им значения f (x₀ ), f (x₁ ), …, f (x_n ). Значения f (x_i ) вычисляются только в случае, если известна функция f (x), но эти значения могут быть получены, например, экспериментальным путем как значение некой неизвестной функции.

Точки x_i , в которых известны значения функции, носят названия узлов интерполяции .

Интерполяция заключается в выборе функции φ (х), значения которой в узлах интерполяции совпадают со значениями f (x_i ).

Между узлами значения этих функций могут отличаться (рисунок 3.1).

Рисунок 3.1 – Интерполяция

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

3.2 Многочлен Лагранжа

Пусть известны значения некоторой функции f в n+1 различных точках. Возникает задача приближенного восстановления функции f в произвольной точке x. Часто для решения этой задачи строится алгебраический многочлен L_n (x) степени n, который в точках x_i принимает заданные значения, т.е.

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

В частности, мы рассматриваем построение интерполирующего многочлена Лагранжа.

,

f_i — значения интерполируемой функции в i-том узле;

— коэффициент интерполяции Лагранжа

.

Можно сказать, что L₁ (x) — линейная функция x, поэтому такую интерполяцию называют линейной (она производится для двух точек).

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

Обратная интерполяция заключается в построении зависимости x (y) и, затем, с помощью такого многочлена легко можно найти корень нелинейного уравнения.

Многочлен Лагранжа в этом случае выглядит следующим образом:

,

— коэффициент интерполяции Лагранжа

.

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

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

3.3 Интерполяция сплайнами

Пусть отрезок [a, b] разбит на n одинаковых частей точками x₀ , x_1, …x_n .

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

Например, линейная интерполяция — это сплайн первого порядка с дефектом 1.

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

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

Этот сплайн не прерывен вместе с первой производной, но непрерывность второй производной не гарантируется, т.е. дефект сплайна равен 2. Если этот сплайн имеет непрерывную вторую производную на отрезке [a, b], т.е. имеет дефект 1, то такой сплайн носит название глобального.

Для построения кубического сплайна используется формула:

Для построения глобального сплайна, т.е. сплайна с дефектом 1 необходимо, начиная со 2-го узла, поставить условие непрерывности 2-й производной, т.е.2-я производная при подходе к точке 2 и дальше слева (x₁ -0) должна равняться второй производной при подходе справа (x₁ +0).

Такие равенства можно составить для всех внутренних узлов x₁ до x_{n -1} . Затем используем условия на краях x₀ и x_n , получаем систему уравнений, которая и обеспечит дефект 1.

Очевидно, что при наличии S3 на соответствующих участках, построение таких равенств не представляет особого труда.

Приравнивая эти значения, для определения m получим СЛАУ.

В двух крайних точках:

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

3.4 Использование интерполяции на практике

3.4.1 Интерполяция с помощью многочлена Лагранжа

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

Составляем таблицу узлов интерполяции:

Поскольку n=5 строим интерполяционный многочлен L₅ (x):

L₅ (x) =P₅₀ *f (x₀ ) +P₅₁ *f (x₁ ) + P₅₂ *f (x₂ ) + P₅₃ *f (x₃ ) + P₅₄ *f (x₄ ) + P₅₅ *f (x₅ )

В результате получаем многочлен:

L₅ (x) = 1.049*10 -3 *x 5 +5.4373*10 -3 *x 4 +0.027*x 3 — 0,936*x 2 + 0,424*x +0.42278, X= — 0.48051

Подставляя заданное значение аргумента, получаем ответ:

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

f (-0.48051) =0.00011

3.4.2 Обратная интерполяция

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

Составляем таблицу узлов интерполяции:

Поскольку n=4 строим интерполяционный многочлен L₄ (y):

В результате получаем многочлен:

L₄ (y) = 7.99*y 4 -0.8176*y 3 — 0.4932* y 2 +0.9008*y — 0.4759

Подставляя заданное значение функции, получаем ответ:

Таким образом, получаем приближенное значение корня:

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

f (-0,47591) = 0.00625

3.4.3 Интерполяция сплайнами

На участке [b,b+2] выбрать 3 точки (b,b+1,b+2), построить два сплайна на двух отрезках, убедиться в том, что в точке b+1 производная не терпит разрыва.

Для построения сплайна используем формулы:

h=

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

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

Приравнивая эти значения, получаем:

Для нашей функции получаем:

0.42435

— 2.10346

После того, как мы нашли m₁ , можем построить графики (рисунок 3.2).

Рисунок 3.2 — Глобальная интерполяция сплайнами

Также можно сравнить с графиком самой функции (рисунок 3.3).

Рисунок 3.3 — Сравнение графика функции и глобальной интерполяции

3.5 Программа для использования интерполяции

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

Листинг программы представлен в приложении В.

Рисунок 3.4 — Программа для использования интерполяции сплайнами

4. Итерационные методы решения систем линейных алгебраических уравнений

4.1 Общие сведения

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

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

4.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А — матрица. (1)

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

x_k → x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

, или .

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

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

В результате получим систему:

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

Итерационный процесс продолжается до тех пор, пока значения х₁ ( k), х₂ ( k), х₃ ( k) не станут близкими с заданной погрешностью к значениям х₁ ( k-1), х₂ ( k-1), х₃ ( k-1).

4.2.2 Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

,

,

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить.

4.2.3 Программа для решения СЛАУ методом простых итераций

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

Листинг программы приведен в приложении Г.

Рисунок 4.1 — Программа «Метод простых итераций»

4.3 Метод Зейделя

4.3.1 Описание метода

В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) — й итерации компоненты приближения вычисляются по формулам:

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

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

, либо

4.3.2 Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью .

Эту систему можно записать в виде:

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

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить.

4.3.3 Программа дл решения СЛАУ методом Зейделя

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

Листинг программы приведен в приложении Г.

Рисунок 4.2 — Программа «Метод Зейделя»

4.4 Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации: