Чисельні методи для вирішення нелінійних рівнянь

Міністерство загальної та професійної освіти Російської Федерації
Саратовський державний технічний університет

Чисельні методи розв'язування нелінійних РІВНЯНЬ

Методичні вказівки
до самостійної роботи з курсу «Вища математика»
для студентів всіх спеціальностей
під контролем викладача
Схвалено
редакційно-видавничим радою
Саратовського державного
технічного університету
Саратов 2008

Введення
Дана робота орієнтована на вивчення деяких чисельних методів наближеного розв'язання систем нелінійних рівнянь з будь-яким числом рівнянь, складання на базі цих методів обчислювальних схем алгоритмів і програм алгоритмічною мовою ФОРТРАН - IV.
Методичні вказівки можуть бути використані як в процесі виконання курсової роботи, так і для вирішення практичних завдань.
Завдання справжніх вказівок полягає в тому, щоб навчити студентів розв'язувати системи нелінійних рівнянь за допомогою ЕОМ і потім отримані навички використовувати в курсовому і дипломному проектуванні.
Передбачається, що студенти прослухали лекційний курс з основ алгоритмічної мови ФОРТРАН - IV.
В якості довідкового посібника з мов програмування може бути використана література. [5]

Чисельні методи для вирішення нелінійних рівнянь
Мета роботи: вивчення чисельних методів наближеного рішення нелінійних систем рівнянь, складання на базі обчислювальних схем алгоритмів; програм алгоритмічною мовою ФОРТРАН - IV, придбання практичних навичок налагодження і вирішення завдань з допомогою ЕОМ.
1. Визначення і умовні позначення
- Конечномерное лінійний простір, елементами (точками, векторами) є групи з впорядкованих дійсних чисел, наприклад:

де - Дійсні числа, .
У введена операція додавання елементів, т. е. визначено відображення ,
де
Воно має такі властивості:
1. ,
2. ,
3. , Що (Елемент називається нульовим),
4. , Що (Елемент називається протилежним елементу ).
У введена операція множення елементів на дійсні числа, тобто визначено відображення ,
де
Воно має такі властивості:
1. ,
2.
Операції складання елементів і множення їх на числа задовольняють законам дистрибутивності:
1. ,
2. .
Кожній парі елементів поставлено у відповідність дійсне число, що позначається символом і зване скалярним добутком, де

і виконані наступні умови:
1. ,
2. ,
3. ,
4. , Причому - Нульовий елемент.
Матриця виду
, (1)

де - Дійсні числа ( , ) Визначає лінійний оператор, що відображає лінійний простір в себе, а саме, для
,
де .
Над лінійними операторами, що діють в лінійному просторі , Вводяться наступні операції:
1. складання операторів , При цьому, якщо , То ,
2. множення операторів на числа: при цьому, якщо , То ,
3. множення операторів: , При цьому, якщо , То .
Зворотним до оператора називається оператор такий, що , Де - Одиничний оператор, який реалізує тотожне відображення, а саме,
.
Нехай число і елемент , Такі, що .
Тоді число називається власним числом лінійного оператора , А елемент - Власним вектором цього оператора, відповідним власним числа .
Лінійний оператор називається зв'язаним до оператора , Якщо для будь-яких елементів виконується рівність .
Для будь-якого оператора пов'язаний оператор існує, єдність; якщо , То .
Справедливі рівності:
1. ,
2. ,
3. ,
4. , Якщо існує.
Кожному елементу ставиться у відповідність дійсне позитивне число, що позначається символом і зване нормою елемента .
Введемо в розгляд три норми для :
,
,
.
При цьому виконуються наступні нерівності:
.
Норма елемента задовольняє таким умовам (аксіомам норми):
1. , Причому , Лише якщо ,
2. ,
3. .
Кажуть, що послідовність елементів сходиться до елемента ,
а саме, ,
або ,
якщо .
Визначена таким чином збіжність в скінченновимірному лінійному просторі називається збіжністю за нормою.
Безліч елементів , Що задовольняють нерівності називається замкнутим (відкритим) кулею в просторі з центром в точці і позначається .
Кожному лінійному оператору, який визначається квадратною матрицею (1), ставиться у відповідність дійсне невід'ємне число, позначуване символом і зване нормою лінійного оператора .
Норма лінійного оператора задовольняє таким умовам аксіомам норм:
4.4 , Причому , Лише якщо - Нульова матриця,
4.4 ,
4.4 .
Введемо в розгляд три норми для А що відображає в :
,
,
,
де i - е власне значення матриці .
Ці норми лінійного оператора А погоджені з відповідними нормами елемента (вектора) в сенсі умови .

2. Основні відомості про системи нелінійних рівнянь в
Загальна форма систем нелінійних рівнянь в має вигляд:
(2)
або F (x) = 0,
де - Задані функції n змінних, - Невідомі.
Функція при дійсних значеннях аргументів беруть дійсні значення, тобто є действітельнозначнимі. Обчислювати будемо тільки дійсні рішення.
Рішенням системи нелінійних рівнянь (2) називається сукупність (група) чисел , Які, будучи підставлені на місце невідомих , Звертають кожне рівняння системи в тотожність.
Окремим випадком системи (2) є система лінійних рівнянь:

або ,
де А - матриця виду (1), що породжує лінійний оператор, що відображає в


Система лінійних рівнянь (2) поставимо у відповідність лінеаризовані рівняння (перші два члени з розкладання в ряд Тейлора (2)) в точці виду
(2 )
або ,
де - Квадратна матриця Якобі, складена з приватних похідних першого порядку функцій, а саме , Обчислених точці .
Для подальшого нам буде потрібно ще одна форма запису системи нелінійних рівнянь в , А саме:
(3)
або ,
де .
Операції, з допомогою яких здійснюється перетворення системи (2) до системи (3), можуть бути будь-якими, необхідно тільки, щоб дані рішення системи (3) задовольняло системі (2).
Функції задовольняють тими самими умовами, що й функції .

3. Відділення рішень
Завдання відділення розв'язків систем нелінійних рівнянь полягає у визначенні досить малої околиці (кулі малого радіуса, центром якого є рішення) біля якого-небудь одного рішення і у виборі в цій околиці початкового наближення до вирішення. Початкове наближення має потрапити при цьому в область збіжності методу.
Завдання відділення рішень не має достатньо ефективних методів загального характеру. При вирішенні рівняння передбачається знання початкових наближень до ізольованого рішенням з постановки конкретного завдання. Якщо ж таких даних немає, то можна дати лише деякі рекомендації для конкретних видів рівнянь.
Так, якщо дано скалярний рівняння , То його рішення з геометричної точки зору можна розглядати як абсциси точок перетину графіка функції з віссю абсцис. Побудувавши графік функції y = f (X), наближено визначаємо околиці ізольованих точок перетину графіка з горизонтальною віссю. Самі точки перетину беремо за початкові наближення до точних рішень.
Безумовно, графічні побудови мають великі похибки, і вибрані початкові наближення можуть не потрапити в область збіжності застосовуваного методу.
Тоді потрібно провести пробні рішення на ЕОМ обраним методом з дослідженням збіжності.
Якщо наближення сходяться, то початкові наближення обрані в області збіжності методу і можна отримати наближене рішення із заданою точністю.
Якщо наближення розходяться, слід провести більш точні графічні побудови і вибрати початкове наближення в області збіжності.
Аналогічно відокремлюються рішення для системи двох нелінійних рівнянь
, .
У цьому випадку на площині x, y будуються лінії рівня функції двох змінних і . Координати точок перетину графіків цих функцій дають початкові наближення ізольованих рішень.

4. Методи рішення нелінійних рівнянь
4.1 Метод простої ітерації
Метод простої ітерації (див. [1]) застосовується для розв'язання систем нелінійних рівнянь з будь-яким числом рівнянь. Його можна застосовувати як для уточнення знайденого рішення, так і для початкового знаходження рішення. В останньому випадку, однак, метод може не дати результату.
Для застосування методу простої ітерації система рівнянь (2) приводиться до вигляду (3).
Потім, узявши початкове наближення , Яке передбачається або відомим, або довільним, будуємо послідовність
(4)
за наступними формулами
(5)
Зауваження. Для приведення системи рівнянь (2) до виду (3) можна використовувати прийом:

де - Релаксаційний параметр, визначається методом Зейделя.
4.2 Метод Зейделя
Метод Зейделя відрізняється від методу простої ітерації тим, що обчислення ведуться за формулами:
(6)
Іншими словами, при обчисленні використовуються не , Як у методі простої ітерації, а .
4.3 Метод Ньютона
Цей метод (див. [1], [4]) запропонований І. Ньютоном в 1669 році, проте найбільш повне обгрунтування було зроблено радянським математиком Л. В. Канторовичем в 1949 році (див. [4]), тому в літературі цей метод часто називають методом Ньютона-Канторовича.
Метод Ньютона є одним з ітераційних методів, одержуваних лінеаризацією лінійного оператора
,
де з рівняння (2).
Так, для к-го наближення до точного розв'язання рівняння (2) ставиться у відповідність лінеаризовані рівняння виду (2 ), А саме:

або ,
де - Квадратна матриця Якобі, складена з приватних похідних першого порядку функцій, тобто , Обчислених в точці .
Таким чином, послідовність (4) будується за такими правилами:
(),
де - Зворотний оператор до лінійного оператора , Який визначається квадратною матрицею


Труднощі побудови алгоритму методу Ньютона, пов'язані з обігом похідної (Побудова ), Зазвичай долаються тим, що замість методів звернення матриці вирішують алгебраїчну систему рівнянь (7) відносно невідомих . Алгоритми розв'язку системи лінійних алгебраїчних рівнянь добре відпрацьовані, для них є стандартні програми для ЕОМ і, крім того, у результаті рішення системи одночасно із зверненням матриці виходить множення оберненої матриці на вектор .
Ітераційна формула методу Ньютона при такому підході буде мати вигляд:
(7)
. (8)
4.4 Модифікований метод Ньютона
Цей різновид методу Ньютона будується шляхом визначення похідної тільки в одній точці наближеного рішення, тобто Послідовні наближення (4) будуються за формулами:
, (9)
де - Початкове наближення до точного розв'язання .

4.5 Метод Зейделя на основі Лінеаризовані рівняння
Ітераційна формула для побудови наближеного розв'язку нелінійного рівняння (2) на основі Лінеаризовані рівняння (7) має вигляд:

4.6 Метод найшвидшого спуску
Методи спуску (див. [2]) зводять рішення системи (2) до задачі знаходження мінімуму спеціально побудованого функціоналу (функціонал - відображення в R), а саме:
,
де .
Функціонал в кінцевому просторі R ⁿ можна розглядати як функцію багатьох змінних .
Для знаходження точки , В якій функціонал f приймає мінімальне нульове значення, обирають точку , Знаходять і будують итерационную формулу: з початковим наближенням .
У ітераційної формулою параметр h _k поки не визначений, виберемо його таким чином, щоб виконалось умова: , Починаючи з x ^0, в припущенні, що f - монотонний функціонал.
Для вибору h _k побудуємо функціонал, що залежить від параметра, який змінюється безупинно: .
При h = 0 маємо, що f (0) - лінія рівня функціонала, що проходить через точку x ^k. Для знаходження наступної лінії рівня, ближчою до мінімуму, будемо вибирати h таким чином, щоб для даного x ^k

Ця умова мінімуму по h будемо розглядати як рівняння для отримання h _k.
Вирішимо його наближено, тому що помилка в кілька відсотків звичайно не впливає на швидкість збіжності. Відзначимо до речі, що число h _k завжди має бути позитивним. Для цього розкладемо функцію в ряд Тейлора з h в точці h = 0 і візьмемо тільки лінійну частину цього розкладу
.
Підстановка лінійної частини в умова , Дає рівняння для наближеного визначення
.
Вирішуючи побудоване рівняння відносно h, отримаємо:
або .

Таким чином, итерационная формула методу найшвидшого спуску має вигляд:
або , Де похідні обчислені в точці .
Метод найшвидшого спуску вимагає більшої кількості обчислень, ніж інші методи першого порядку. Але він має в порівнянні з іншими методами важливою перевагою, що полягає в неминучій збіжності процесу. При цьому потрібно пам'ятати, що метод найшвидшого спуску може призвести не до розв'язання системи рівнянь (2), а до значень аргументу, що дає відносний екстремум функції
, Тобто .

5. Збіжність методів розв'язання нелінійних рівнянь
Якщо метод сходиться, тобто , Де
- Точне рішення
- K-те наближення до точного розв'язання, то ітераційний процес слід було б закінчити по досягненню заданої похибки , Де e - задана точність (похибка).
Проте практично це умова виконати не можна, так як невідомо, тоді для закінчення ітераційного процесу можна скористатися нерівностями , Або , Де і - Задані величини.
При такому закінчення ітерацій похибка може зрости в порівнянні з і, тому, щоб не збільшувалася, величини і відповідно зменшують або збільшують число ітерацій.
Методи простої ітерації, Зейделя, модифікований метод Ньютона, метод найшвидшого спуску (див. [1], [2], [3], [4]) є методами першого порядку - це означає, що має місце нерівність , K = 1, 2,. . . , Де - Константа, своя у кожного методу, що залежить від вибору початкового наближення , Функції f _i , i = 1, 2,. . . , N, і їх приватних похідних першого і другого порядків - точніше їх оцінок в деякій околиці шуканого рішення, якій належить початкове наближення.
Метод Ньютона є методом другого порядку, тобто для нього має місце нерівність , K = 1, 2,. . . , Де - Константа, що залежить від тих же величин, що і константа .
А тепер розглянемо достатні умови збіжності методу простої ітерації і методу Ньютона.
Збіжність процесу простої ітерації залежить від двох умов. Перша умова полягає в тому, що яка-небудь точка повинна виявитися близькою до вихідного рішенням . Ступінь необхідної близькості залежить від функцій j _1, j _2,. . . , J _n . Ця вимога не відноситься до систем лінійних рівнянь, для яких збіжність процесу простої ітерації залежить тільки від другої умови.
Друга умова пов'язана з матрицею, складеною з приватних похідних першого порядку функцій j _1, j _2,. . . , J _n - Матрицею Якобі
,
обчислених в точці .
У випадку, коли розглядається система лінійних алгебраїчних рівнянь, матриця M складається з постійних чисел - коефіцієнтів, що стоять при невідомих у правій частині рівняння (3). У випадку нелінійних рівнянь елементи матриці M залежать, взагалі кажучи, від . Для збіжності процесу простої ітерації достатньо, щоб виконувалося нерівність: для з деякої околиці точного рішення , Якій має належати початкове наближення .
Наведемо також достатні умови збіжності методу Ньютона для системи рівнянь виду (2) за нормою .
Припустимо, що є початкове наближення до шуканого розв'язку системи (2) , Функції безупинні і мають безперервні приватні похідні до другого порядку в кулі , Тоді, якщо виконані умови:
1) Матриця Якобі системи (2) на початковому наближенні має зворотну і відома оцінка норми зворотної матриці ,
2) Для всіх точок кулі виконано нерівність
при i, j = 1, 2,. . . , N,
3) Виконано нерівність
,
де L - постійна 0 £ L £ 1,
4) Числа b, N, r підпорядковані умові a = NbNr <0,4, тоді система рівнянь (2) в кулі має єдине рішення, до якого сходяться послідовні наближення (8) або ( 7 ' ), ( 9 ' ).
Для інших методів умови збіжності мають складний вид, і ми відсилаємо читача до спеціальної літератури [1], [2], [3], [4].

6. Примірний перелік можливих досліджень
1) Порівняння різних методів на економічність при вирішенні конкретного завдання:
· За кількістю операцій на одній ітерації;
· За кількістю ітерацій, необхідних для досягнення заданої точності;
2) Залежність числа ітерацій для досягнення заданої точності:
· Від вибору виду норми;
· Від вибору критерію закінчення ітераційного процесу з або за невязке ;
· Від вибору початкового наближення;
· Від похибки завдання коефіцієнтів в рівнянні.

7. Контрольні питання
1) Поняття про нелінійних системах рівнянь в R ^n.
2) Поняття наближеного й точного рішення нелінійної системи рівнянь.
3) Сутність графічного методу відділення рішення для системи двох нелінійних рівнянь, які його переваги та недоліки?
4) Сутність методу простої ітерації і методу Зейделя. Які умови застосовності методу простої ітерації?
5) Сутність методу Ньютона і його модифікації. Яка швидкість збіжності методу Ньютона?
6) Суть методу найшвидшого спуску. Як вибирається параметр узвозу?

8. Порядок виконання курсової роботи
1) Отримати варіант завдання, індивідуальний для кожного студента, у викладача, а саме:
Знайти рішення системи нелінійних рівнянь в першій координатній чверті з номером - N ₁ (див. варіанти завдань п.10), застосувавши для першого етапу уточнення метод з номером - N _2, а для другого етапу уточнення метод з номером - N ₃ , Точність обчислень на першому етапі - EPS1Î [0.1 - 0.01], на другому етапі - EPS2 Î [0.1 - 0.0001], N ₄ - номер норми, I - номер параметра a, J - номер параметра b, початкове наближення вибрати довільно або графічно , aÎ (0,1).
2) Розробити обов'язкові для виконання завдання розділи даних методичних вказівок.