Системи нелінійних рівнянь

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСИТЕТ

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

З дисципліни
«Чисельні методи»

Тема проекту:
« Системи нелінійних рівнянь»

Виконала:

студентка групи КН-II-2

Омельченко Ю.В.

Київ 2008

Зміст

Вступ

Розділ 1 Чисельні методи розв’язання систем нелінійних рівнянь

1.1 Нелінійні рівняння

1.2 Система нелінійних рівнянь

1.3 Метод простих ітерацій

1.4 Метод Ньютона

1.5 Модифікований метод Ньютона

Розділ 2 Практичне використання методів розв’язання систем нелінійних рівнянь

2.1 Розв’язання систем нелінійних рівнянь у пакеті Mathcad

2.2 Розв’язання систем нелінійних рівнянь у пакеті Excel

2.3 Розв’язання систем нелінійних рівнянь на мові С++

Висновок

Список використаної літератури

Вступ

З розвитком нової обчислюваної техніки інженерна практика наших днів більш часто зустрічається з математичними задачами, точне вирішення яких отримати досить складно чи неможливо. В цих випадках звичайно застосовують ті чи інші наближенні обчислення. Ось чому наближені та чисельні методи математичного аналізу отримали за останні роки широкий розвиток і набули виключно важливе значення.

Нові обчислювальні засоби спричинили переоцінку відомих методів вирішення задач з точки зору доцільності їх реалізації на ЕОМ і стимулювали створення більш ефективних.

Предметом вивчення обчислювальної математики є чисельні методи вирішення задач математичного аналізу: вивчення алгоритму метода, умови збіжності ітераційних методів, вивчення границь використання методів, дослідження оцінки похибки методів і обчислень. Головним розділом обчислювальної математики є реалізація чисельних методів на ЕОМ, тобто створення програми для потрібного алгоритму і вирішення конкретної задачі за допомогою складеної програми.

У даній курсовій роботі я розгляну чисельні методи розв’язання систем нелінійних рівнянь. Серед них метод простих ітерацій та метод Ньютона в різних модифікаціях. Ці методи реалізовані в Mathcad, Excel та на мові програмування С++.

Розділ 1 Чисельні методи розв
’
язання систем нелінійних рівнянь

1.1 Нелінійні рівняння

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

. (1.1.1)

Тут - нелінійна функція:

– Нелінійна алгебраїчна функція виду ;

– Трансцендентні функції – тригонометричні, обернені тригонометричні, логарифмічні, показникові и гіперболічні функції;

– комбінування цих функцій .

Розв’язком нелінійного рівняння (1.1.1) є така точка , яка при підстановці у рівняння (1.1.1) перетворює його у тотожність. На практиці не завжди вдається підібрати такий розв’язок. В цьому випадку, розв’язок рівняння (1.1.1) знаходиться із застосуванням наближених (чисельних) методів. Тоді розв’язком нелінійного рівняння (1.1.1) буде така точка , при підстановці якої у рівняння (1.1.1) останнє буде виконуватися з певним степенем точності, тобто , де - мала величина. Знаходження таких розв’язків складає основу чисельних методів і обчислюваної математики.

Розв’язання нелінійних рівнянь складається з двох етапів:

1) відокремлення коренів;

2) уточнення коренів нелінійних рівнянь.

На першому етапі необхідно дослідити рівняння і з’ясувати є корні чи ні. Якщо корні є, то скільки їх, і потім з’ясувати інтервали, в кожному з яких знаходиться єдиний корінь.

Перший спосіб відокремлення коренів – графічний. Виходячи із рівняння (1.1.1), можна побудувати графік функції . Тоді точка перетину графіка з віссю абсцис є приближенням значення кореня. Якщо має складний вигляд, то представимо її у вигляді різниці двох функцій . Так як , то виконується рівність . Побудуємо два графіки , . Значення - приблизне значення кореня (Рис.1), яке є абсцисою точки перетину двох графіків.

Другий спосіб відокремлення коренів нелінійних рівнянь – аналітичний.
Процес відокремлення коренів нелінійних рівнянь базується на наступних теоремах.

Теорема 1. Якщо функція неперервна на відрізку і змінює на кінцях відрізка знак (тобто ), то на міститься хоча б один корінь.

Теорема 2. Якщо функція неперервна на відрізку , виконується умова вигляду і похідна зберігає знак на , то на відрізку міститься єдиний корінь.

Теорема 3. Якщо функція є многочленом степені і на кінцях відрізка змінюється знак, то на міститься непарна кількість коренів (якщо похідна зберігає знак на , то корінь єдиний). Якщо на кінцях відрізка функція не змінює знак, то рівняння (1.1.1) або не має коренів на , або має парну кількість коренів.

При аналітичному методі дослідження необхідно з’ясувати інтервали монотонності функції . Для цього необхідно обчислити критичні точки , тобто точки, у яких перша похідна дорівнює нулю чи не існує. Тоді вся числова вісь розбивається на інтервали монотонності . На кожному із них з’ясовується знак похідної , де . Потім виділяємо ті інтервали монотонності, на яких функція змінює знак. На кожному із цих інтервалів для пошуку кореня використовуються методі уточнення коренів.

1.2 Система нелінійних рівнянь

Система нелінійних рівнянь має вигляд:

(1.2.1)

Тут - невідомі змінні, а система (1.2.1) називається звичайною системою порядку , якщо хоча б одна із функцій нелінійна.

Розв’язання систем нелінійних рівнянь – одна із складних задач обчислювальної математики. Складність полягає у тому, щоб з’ясувати: чи має система розв’язок, і, якщо – так, то скільки. Уточнення розв’зків у заданій області – більш проста задача.

Нехай функції визначені в областях . Тоді область і буде тією областю, де можна знайти розв’язок. Найбільш відомими методами уточнення розв’язків є метод простих ітерацій та метод Ньютона.

1.3 Метод простих ітерацій

Із вихідної системи (1.2.1) шляхом еквівалентних перетворень переходимо до системи виду:

(1.3.1)

Ітераційний процес, який визначається формулами

,

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

чи .

Розпишемо першу умову:

при

при .

Розпишемо другу умову:

при

при .

Розглянемо один із способів приведення системи (1.2.1) до виду (1.3.1), допустиме збіжній ітерації.

Нехай задана система другого порядку виду:

.

Потрібно привести її до виду:

.

Множимо перше рівняння системи на невідому постійну , друге - на , потім додаємо їх і добавляємо в обидві частини рівняння . Отримаємо перше рівняння перетвореної системи

де .

Далі, помножимо перше рівняння системи на невідому сталу , друге - на , потім додамо їх і добавляємо в обидві частини рівняння . Тоді друге рівняння перетвореної системи буде мати вид

де .

Невідомі сталі визначимо з допустимі умови збіжності

и .

Запишемо ці умови більш детально:

Припустимо, що вирази під знаком модуля дорівнюють нулю, і отримаємо систему з чотирьох рівнянь з чотирма невідомими для визначення сталих :

.

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

Щоб розв’язати систему, потрібно задати початкове приближення и обчислити значення похідних і , в цій точці. Обчислення здійснюється на кожному кроці ітерацій, при цьому , ,.

Метод простих ітерацій є найбільш універсальним і простим для реалізації на ЭОМ. Якщо система має великий порядок, то застосування даного метода, який має повільну швидкість збіжності, не рекомендується. В цьому випадку, використовують метод Ньютона, який має швидшу збіжність.

1.4 Метод Ньютона для розв
’
язання

Нехай () — деяка послідовність невироджених n-матриць. Тоді, очевидно, послідовність задач

, k = 0,1,2,...

маємо ті ж розв’язки, що і вихідне рівняння F(x)=0, і для приближеного знаходження цих розв’язків можна формально записати ітераційний процес

, k = 0,1,2,... (1.4.1)

Який має вигляд метода простих ітерацій (1.3.1) при . У випадку - це дійсно МПІ з лінійною збіжністю послідовності () Якщо же різні за різних k, то формула (1.4.1) визначає велику кількість ітераційних методів з матричними параметрами. Розглянемо деякі з цих методів.

Припустимо , де

— матриця Якобі вектор-функція F(x). Підставимо це в (1.4.1), отримаємо явну формулу метода Ньютона

, (1.4.2)

Цю формулу, що вимагає перетворення матриць на кожній ітерації, можна переписати в неявному вигляді:

. (1.4.3)

Використання (1.4.3) припускає при кожному k = 0,1,2,... розв’ язок лінійної алгебраїчної системи

відносно векторній поправці , а потім добавлення цієї поправки до поточного наближення для отримання наступного:

.

До розв’язку таких лінійних систем можна використовувати найрізноманітніші методи як прямі, так і ітераційні в залежності від розмірності n розв’язуваної задачі і специфіки матриць Якобі .

Порівнюючи (1.4.3) з формальним розкладом F(x) в ряд Тейлера

,

бачимо, що послідовність () в методі Ньютона отримується в результаті заміни при кожному k=0,1,2,... нелінійного рівняння F(x) = 0 чи, при допустимій гладкості F(x)), рівняння

лінійним рівняння

тобто з покроковою лінеаризацією. Як наслідок цього факту, можна полягати, що при допустимій гладкості F(x) і достатньо гарному початковому наближенні збіжність, яка виникає методом Ньютона послідовності () до розв’язку буде квадратичною і в багаторазовому випадку.

Новим, порівняно з скалярним випадком, фактором, який ускладнює використання метода Ньютона до розв’язання n-вимірних систем, є необхідність розв’язання n-вимірних лінійних задач на кожній ітерації, обчислення яких збільшується зі збільшенням n, тобто кажучи, непропорційно швидко. Зменшення таких затрат є одним з напрямків модифікації метода Ньютона.

1.5 Модифікований метод Ньютона

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

Якщо матрицю Якобі F'(х) обчислювати і перетворити лише один раз — в початковій точці , то від метода Ньютона (5) перейдемо до модифікованого методу Ньютона

(1.5.1)

Цей метод потребує значно менших обчислень на один ітераційний крок, але ітерації при цьому може потребуватися значно більше для досягнення заданої точності в порівнянні з основним методом Ньютона (1.4.2), оскільки, будучи частковим випадком МПІ (), він має лише швидкість збіжності геометричної прогресії.

Компромісний варіант — це обчислення і перетворення матриць Якобі не на кожному ітераційному кроці, а через декілька кроків (інколи такі методи називаються рекурсивними).

Наприклад, просте чергування основного (1.4.2) і модифікованого (1.5.1) методів Ньютона приводить до ітераційної формули

(1.5.2)

де k = 0,1,2,… За тут приймається результат останнього прийому одного кроку основного, а потім одного кроку модифікованого метода, тобто

(1.5.3)

Доведено, що такий процес при певних умовах призводить до кубічно-збіжних послідовностей ().

Розділ 2

Практичне використання методів розв
’
язання систем нелінійних рівнянь

2.1 Розв
’
язання систем нелінійних рівнянь у пакеті
Mathcad

Оператор
solve

За допомогою символьного процесу Mathcad можна отримати аналітичний розв’язок системи нелінійних рівнянь. Зробити це можливо двома способами. По-перше, можна скористатися оператором solve (розв’язати). В цьому випадку система повинна бути внесена в його лівий маркер у вигляді вектора. Змінні, значення яких повинно бути знайдено, потрібно ввести через кому в правий маркер оператора solve. Відповідь буде повернена у вигляді матриці, в рядках якої будуть записані корні знайдених розв’язків. Їх послідовність буде така ж, якою була послідовність відповідних змінних в правому маркері оператора solve.

Приклад 2.1.1:

Розв’язати систему нелінійних рівнянь:

Розв’язання

Блок
Given-Find

По-друге, можна використати так кажучи обчислювальний блок Given-Find (Given – Дано, Find – розв’язати систему рівнянь).

Щоб розв’язати систему рівнянь за допомогою обчислювального блоку, необхідно виконати наступні дії:

1. Наберіть увідне слово Given.

2. Під увідним словом задайте систему рівнянь.

3. Введіть функцію розв’язання системи рівнянь find(x1,x2,…). В дужках через кому задайте змінні в тій послідовності, в якій повинні бути розташовані у відповіді відповідні корні.

4. В якості оператора виводу результату роботи функції find(x1,x2,…) використовуйте оператор символьного виводу « → ». Якщо ж використати оператор виводу « = », то для розв’яку системи, при умові добавлення початкових наближень, буде запущено один із чисельних алгоритмів.

Приклад 2.2.1

Розв’язати систему нелінійних рівнянь:

Розв’язок:

Графічна ілюстрація:

Приклад 2.2.2

Розв’язати систему нелінійних рівнянь:

Розв’язання

Розв’язок:

Приклад 2.2.3

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

Приклад 2.3.1

Розв’язок:

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

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

Приклад 2.4.1

Розв’язок:

Перевірка:

Модифіковані методи Ньютона

Приклад 2.5.1

Вектор-матриця заданої системи:

Матриця Λ

Розв’язок:

Приклад 2
.5.2

Вводимо вектор-функцію системи рівнянь:

Функція iter(x,y) обчислює наближення до кореня за формулою Ньютона:

Функція norma(x,y,x1,y1) обчислює норму між поточним і наступним: наближенням:

Функція Newton(x,y,eps) знаходить розв’язок системи рівнянь з точність до ерs:

Початкове наближення х=0, у=-1, eps=0.001

Розв’язок системи:

2.2 Розв’язання систем нелінійних рівнянь у пакеті

Excel

Також систему нелінійних рівнянь можна розв’язати у пакеті Excel. Саме засіб Пошук рішення
дозволяє знаходити рішення систем нелінійних рівнянь. Продемонструю, як це робиться на прикладі рішення наступної системи рівнянь:

Нагадаємо, що пари (х, у) є рішенням системи (*) тоді і тільки тоді, коли вона є рішенням наступного рівняння з двома невідомими:

(**)

За допомогою засобу Пошук рішення замість системи (*) треба розв‘язувати рівносильне їй рівняння (**). Помітимо, що геометрично розв‘язок система рівнянь (*) описують точки перетину прямої з колом, радіус якого дорівнює (≈2,236). Отже, рівняння (**) має не більш двох різних розв‘язків.

Знайдений засобом Пошук рішення розв‘язок нелінійної задачі залежить від початкового наближення. Тому істотним є вдалий його підбір. У даному випадку локалізувати корені можна, наприклад, протабулювавши ліву частину рівняння (**) по змінних х і у на інтервалі [-2,25; 2,25] із кроком 0.5. Вибір проміжків табуляції визначаються величиною радіуса кола, що дорівнює (≈2,236), а корені рівняння лежать усередині цього кола.

Виконаєте наступні кроки:

1. В чарунки діапазонів А2:А11 і B1:К1 уведіть значення змінних х та у, відповідно, використовуючи команду Правка│Заповнити│Прогресія.

2. В чарунку В2 введіть формулу

=($А2^2+У$1^2-5)^2+(5*$А2-4*B$1-1)^2, яка дає результат обчислення значення правої частини рівняння (**) при значеннях х и у з чарунок А2 і B1, відповідно.

3. Виберіть чарунку В2, розташуєте покажчик миші на маркері заповнення і заповните діапазон В2:К11.

Рис. 3.1 - Результат табуляції лівої частини рівняння (**) і діалогове вікно Пошук рішення

Отже, права частина рівняння протабульована. З рис. 5.15 видно, що за початкове наближення до коренів можна взяти ті значення, що виділені кольором.

Тепер можна зробити підготовчу роботу перш, ніж знайти корені за допомогою засобу Пошук рішення
.

1. Відведіть чарунки А16:В16 під невідомі х и у для знаходження першого кореня, а А17:В17 — для знаходження другого кореня.

2. Уведіть відповідні значення змінних і розрахункові формули в чарунки А16:С16 і А17:С17

3. Виберіть команду Сервіс | Пошук рішення
і заповните діалогове вікно Пошук рішення
, як показано на рис. 3.1.

2. Натисніть кнопку Виконати. Засіб Пошук рішення знайде шукані максимально наближені корені рівняння.

3. Аналогічно знайдіть другий корінь. Результати розрахунку приведені на рис. 3.2.

Рис.
3
.
2
– Корені рівняння

Приклад 3.1:

	A	B	C	D	E	F	G	H	I	J	K
1		-2,25	-1,75	-1,25	-0,75	-0,25	0,25	0,75	1,25	1,75	2,25
2	-2,25	36,83	37,33	55,20	85,95	126,58	175,58	232,95	300,20	380,33	477,83
3	-1,75	10,33	8,83	22,70	47,45	80,08	119,08	164,45	217,70	281,83	361,33
4	-1,25	5,70	0,20	8,58	26,33	50,45	79,45	113,33	153,58	203,20	266,70
5	-0,75	18,45	6,95	8,33	18,08	33,20	52,20	75,08	103,33	139,95	189,45
6	-0,25	45,58	26,08	18,95	19,70	25,33	34,33	46,70	63,95	89,08	126,58
7	0,25	85,58	56,08	38,95	29,70	25,33	24,33	26,70	33,95	49,08	76,58
8	0,75	138,45	96,95	68,33	48,08	33,20	22,20	15,08	13,33	19,95	39,45
9	1,25	205,70	150,20	108,58	76,33	50,45	29,45	13,33	3,58	3,20	16,70
10	1,75	290,33	218,83	162,70	117,45	80,08	49,08	24,45	7,70	1,83	11,33
11	2,25	396,83	307,33	235,20	175,95	126,58	85,58	52,95	30,20	20,33	27,83
12
13
14	x	Y	Рівняння
15	-1,27	-1,84	0,00
16	1,52	1,64	0,00

2.3 Розв’язання систем нелінійних рівнянь на мові
С++

Метод простих ітерацій з поліпшенням Зейделя

Текст програми на мові С++:

#include <vcl.h>

#include <math.h>

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

float x1(float x[2]){

return sqrt(1-0.7*x[1]*x[1]);}

float x2(float x[2]){

return (x[1]+tan(x[0]*x[1]+1)-x[1]*x[1]);}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

float x[2],y[2],E,q; int n=2,kmax,k;

x[0]=StrToFloat(Edit1->Text);

x[1]=StrToFloat(Edit2->Text);

E=StrToFloat(Edit3->Text);

kmax=StrToInt(Edit4->Text);

k=0;

do{

k=k+1;

for (int i=0;i<2;i++) y[i]=x[i];

if(x[1]<=-1) {

x[0]=x[0]+2.0/3*(x[0]*x[0]+0.7*x[1]*x[1]-1);

x[1]=-sqrt(tan(x[0]*x[1]+1)); }

if(x[1]>-1 && x[1]<=0) {

x[0]=sqrt(1-0.7*x[1]*x[1]);

x[1]=-sqrt(tan(x[0]*x[1]+1)); }

if(x[1]>=0 && x[1]<1) {

x[0]=x[0]+1.0/3*(x[0]*x[0]+0.7*x[1]*x[1]-1);

x[1]=sqrt(tan(x[0]*x[1]+1)); }

if(x[1]>=1) {

x[0]=x[0]-1.0/3*(x[0]*x[0]+0.7*x[1]*x[1]-1);

x[1]=sqrt(tan(x[0]*x[1]+1)); }

q=1.0/n*(fabs(x[0]-y[0])+fabs(x[1]-y[1])); }

while(q>E && k<kmax);

AnsiString f;

Memo1->Lines->Add("x1 = "+f.sprintf(" %5.10f", x[0]));

Memo1->Lines->Add("x2 = "+f.sprintf(" %5.10f", x[1]));

Memo1->Lines->Add("Достигнутая точность = "+f.sprintf(" %5.10f", q));

Memo1->Lines->Add("Количество итераций: "+IntToStr(k));

}

//---------------------------------------------------------------------------

Вікно виконання програми:

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

Текст програми на мові С++:

#include <vcl.h>

#include <iostream.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#include <stdio.h>

#include <iomanip.h>

#include <math.h>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

double Nuton(double*p,int n,double*x,double X)

{

double s=p[n-1];

for(int i=n-2;i>=0;i--) s=p[i]+(X-x[i])*s;

return s;

}

void Nuton1(double*x,double*y,int n,double*p)

{

for(int j=0;j<n-1;j++) {

p[j]=(y[j+1]-y[j])/(x[j+1]-x[j]);

// cout<<p[j]<<"t";

}

// cout<<"n";

int m=n-1;

int l=2;

int k;

int j;

int i;

for(int i=n-2;i>=1;i--)

{

k=0;

for(j=1;j<=i;j++)

{

p[m]=(p[m-i]-p[m-i-1])/(x[k+l]-x[k]);

// cout<<p[m]<<"t";

m++;

k++;

}

// cout<<"n";

l++;

}

j=0;

for(i=1;i<n;i++)

{

y[i]=p[j];

j=j+(n-i);

}

}

void main()

{

int const n=5,N=(n-1)*n/2;

double x[]={1,2,3,4,5};

double y[n];

for(int i=0; i<n; i++) y[i]=1+2*x[i]+3*pow(x[i],2)+4*pow(x[i],3)+5*pow(x[i],4);

double *p=new double[N];

Nuton1(x,y,n,p);

//for (i=0;i<n;i++) cout<<y[i]<<'t';

double z=1.5;

cout<<Nuton(y,n,x,z)<<'t'<<1+2*z+3*pow(z,2)+4*pow(z,3)+5*pow(z,4)<<'n';

getch();

}

Вікно виконання програми:

Висновок

У даній курсовій роботі я описала методи розв’язання систем нелінійних рівнянь, а також навела приклади їх реалізації. В пакеті Mathcad для розв’язання систем нелінійних рівнянь я використала оператор solve, обчислювальний блок given – find, метод простих ітерацій, метод Ньютона та два модифіковані методи Ньютона, в яких на відміну від метода Ньютона матриця Якобі знаходилась не на кожному кроці, а тільки на початковому.

В пакеті Excel розв’язати систему нелінійних рівнянь можна за допомогою засобу «Пошук рішення», в якому замість системи рівнянь необхідно розв’язати рівносильне їй рівняння. Також моє знання мови програмування С++ дозволило мені продемонструвати приклади розв’язання систем нелінійних рівнянь методом ітерацій та методом Ньютона саме мовою програмування С++.

Список використаної літератури

1. Ю.Ю Тарасевич «Численные методы на Mathcad’e»

2. Д. Гурский, Е. Турбина «Вычисления в Mathcad»

3. Б. Демидович «Основы вычеслительной математики»

4. О. Кваша «Численные методы»

5. В.Н. Тарасов, Н.Ф. Бахарева «Численные методы»