Міністерство загальної та професійної освіти Російської Федерації
Саратовський державний технічний університет Чисельні методи розв'язування нелінійних РІВНЯНЬ
Методичні вказівки
до самостійної
роботи з курсу «Вища математика»
для
студентів всіх спеціальностей
під
контролем викладача
Схвалено редакційно-видавничим радою Саратовського державного технічного університету Саратов 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 n можна розглядати як функцію багатьох змінних
.
Для знаходження точки
, В якій функціонал
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 1 (див. варіанти завдань п.10), застосувавши для першого етапу уточнення метод з номером -
N 2, а для другого етапу уточнення метод з номером -
N 3 , Точність обчислень на першому етапі - EPS1Î [0.1 - 0.01], на другому етапі - EPS2 Î [0.1 - 0.0001],
N 4 - номер норми, I - номер параметра
a, J - номер параметра
b, початкове наближення вибрати довільно або графічно , aÎ (0,1).
2) Розробити обов'язкові для виконання завдання розділи даних
методичних вказівок.