Алгоритм методу Зейделя

Вхідні параметри: B та c - матриця B та вектор правої частини c системы x=Bx+c; n - порядок матриці B;

k - число ітерацій; x0 - вектор початкового наближення.

Функція zeid повертає двовимірний масив розмірності kxn; i-й рядок якого – це i-е наближення.

Результат роботи функції zeid - 10 перших наближень

3.7 Оцінка похибки і міра обумовленості

Припустимо, що матриця системи лінійних рівнянь і вектор правих частин задані неточно і замість пред'явленої до розв’язку системи

AХ=b (3.30)

у дійсності розв’язується деяка інша система

A₁X=b₁, (3.31)

де A₁=A+ , b₁=b+ . Позначимо розв’язки (3.30) і (3.31) через X і X₁ відповідно. Оцінимо похибку розв’язку z = X₁ - X. Підставимо вирази для A₁, b₁ і X₁ у (3.31)

(A+ ) (X+z) = b + .

Віднімаючи (3.30), одержимо

A z + ^.x + ^.z = ,

z = A^-1 ( - ^.x - ^. z),

||z||<=||A^-1||^.(|| || + || || ^. ||x|| + || || ||z||). (3.32)

Якщо малі || || і || ||, то варто очікувати і малості ||z||. Тоді доданок ^. z має більш високий порядок малості. Звідси випливає оцінка похибки

. (3.33)

Досить поширений випадок, коли похибка матриці системи істотно менша похибки правої частини; як модель цієї ситуації будемо розглядати випадок точного задання матриці системи. Тоді, вважаючи = 0 у (3.33), маємо

||z||<=||A^-1||^. || ||. (3.34)

Для якісної характеристики зв'язку між похибками правої частини і розв’язку вводиться поняття обумовленості матриці системи. Абсолютні похибки правої частини і розв’язку системи залежать від масштабів, якими вимірюються ці величини і матриця системи. Тому правильніше характеризувати властивості системи через зв'язок між відносними похибками правої частини і розв’язку. Для відносної похибки розв’язку з (3.34) маємо

. (3.35)

Підставляючи оцінку для ||x|| у (3.35), маємо

. (3.36)

Величину ||A^-1|A|| = condА називають мірою обумовленості матриці. Величина відносної похибки розв’язку при фіксованій величині відносної похибки правої частини може стати як завгодно великою при досить великій мірі обумовленості матриці. Число обумовленості залежить від вибору норми матриці. Будь-яка норма матриці не менша від її найбільшого за модулем власного значення, тобто ||A||>= max | |. Власні значення матриці A і A^-1 взаємно обернені; тому .

Таким чином, .

Системи рівнянь і матриці з великими значеннями мір обумовленості прийнято називати погано обумовленими, а з малими - добре обумовленими. Отже, при розв’язуванні СЛАР на ЕОМ обов’язково виникають похибки заокруглення. Тому фактично маємо розв’язок деякої іншої системи . На практиці важливо знати відносну похибку . Якщо замість брати модель , тобто в ЕОМ задається точно, то з попередніх співвідношень випливає ( - міра невизначеності розв’язку системи при неточних вхідних даних).

Якщо брати систему , в якій збурені лише елементи , а b – точне, то, використовуючи співвідношення - = () , дістаємо (;

cond .

Лема. Якщо С-квадратна матриця така, що , то існує (І+С)^-1, причому ||(І+С)^-1 || .

Доведення.

Оскільки , СЛАР має лише тривіальний розв’язок, що й означає невиродженість матриці І+С.

Теорема. Нехай А – невироджена квадратна матриця. Тоді, якщо X та є відповідно розв’язками систем AХ=b та , де Ã=А+ΔА , причому , то можлива оцінка .

Доведення. Оскільки , то внаслідок леми існує причому

Знайдемо

дістаємо шукане.

Приклад реалізації чисельного алгоритму розв’язання СЛАР на псевдокоді.

//Meтод Зейделя. Вважаємо, що умова збіжності методу перевірена

//повертає норму матриці. А – матриця

NormaMatrix(A):

1 temp:=0

2 for i:=1 to A.lengthi do

3 sum:=0

4 for j:=1 to A.lengthj do

5 sum+=abs(A[i,j])

Done

7 if sum>temp then temp:=sum

Fi

Done

10 return temp

End

//повертає норму вектора. В – вектор

NormaVector(B):

1 sum:=0

2 for i:=1 to B.length do

3 sum+=sqr(abs(B[i]))

Done

5 return sqrt(sum)

End

//повертає обернену матрицю до даної A0 з точністю eps

gaussinv(A0,eps):

//доступна в модулі naz.pas

end

//розв’язує систему методом Зейделя

//A – матриця коефіцієнтів

//B – стовпець вільних членів

//X – вектор відповідей

//eps – точність обчислень

// змінні, що обчислюються, але не повертаються функцією як
// результат можуть бути використані в конкретних реалізаціях // алгоритму

Solve_Zeidel(A,B,X,eps):

1 n:=A.lengthI;

2 for i:=1 to n do //AX=B приводимо до вигляду X=CX+D

3 for j:=1 to n do

4 if i<>j then

5 С[i,j]:=(-1)*A[i,j]/A[i,i]

6 else С[i,j]:=0

Fi

Done

Done

10 delta:=(1-NormaVector(С))*eps/NormaVector(С)

11 for i:=1 to n do //обчислюємо A^-1

12 for j=1 to n do

13 A0[i,j]:=A[i,j]

Done

Done

16 gaussinv(A0,eps)

17 condA:=norma(A)*norma(A0)

18 fault:=(condA*((0.01/norma(B))+(0.01/norma(A))))/(1-
(condA*0.04)/norma(A)); //обчислюємо похибку

19 for i:=1 to n do

20 X[i]:=B[i]

Done

22 k:=0

23 repeat //ітераційний процес

24 k++

25 maxr:=0

26 r:=0

27 for i:=1 to n do

28 xk:=X[i]

29 s:=0

30 for j:=1 to n do

31 s+=C[i,j]*X[j]

32 X[i]:=s+D[i]

Done

34 r:=abs(xk-X[i])

35 if maxr<r then

36 maxr:=r

Fi

Done

39 until maxr<=delta;

end

Питання і завдання до теми

“Розв’язання систем лінійних алгебраїчних рівнянь точними методами”

1 Норми векторів і матриць. Абсолютна й відносна похибки вектора.

2 Обумовленість задачі розв’язання системи лінійних алгебраїчних рівнянь. Оцінка похибки розв’язку за похибками вхідних даних: .

3 Метод Гауса (схема єдиного ділення):опис методу, трудомісткість методу.

4 Метод Гауса з вибором головного елемента за стовпцем (схема часткового вибору): опис методу, його обчислювальна стійкість.

5 Застосування методу Гауса для розв’язання інших задач обчислювальної алгебри.

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

7 Трудомісткість методу прогонки.

8 Матрична форма запису методу Гауса.

9 LU-розкладання матриці. Теорема про можливості застосування LU- розкладання (без доведення).

10 Застосування методу LU- розкладання для розв’язку задач обчислювальної алгебри.

11 Стратегії вибору провідного елемента в методі Гауса.

12 Метод Гаусса із частковим вибором у матричній формі.

13 Обчислити норми векторів:a) , a=(-3, 0, 4, -5); b) , a=(2, 6, 0); c) , a=(-13, 7, -4,

14 Обчислити норми матриць

a) , де A= ,

b) , де A= ,

c) , де A= .

15 Чи є вираз нормою вектора ?

16 Довести властивість норм матриць й : .

17 Нехай . Довести, що , тоді й тільки тоді, коли , де - власні значення матриці .

18 Перевірити справедливість властивостей числа обумовленості:
a) , b) ,

c) .

19 Оцінити кількість правильних значущих цифр розв’язку системи лінійних алгебраїчних рівнянь, якщо матриця системи задана точно, елементи вектора правих частин задані із трьома правильними значущими цифрами, а .

Питання і завдання до теми “Розв’язання систем лінійних алгебраїчних рівнянь ітераційними методами”

1 Розв’язати систему методом простої ітерації (методом Якобі) з точністю 0.01.

2 Зробити 3 ітерації за методом Зейделя, попередньо перетворивши системи до вигляду, зручного для ітерації. За початкове наближення взяти нульовий вектор. Зобразити графічно поведінку ітераційного процесу. Проаналізувати отримані результати з погляду збіжності (розбіжності) методу.

, ,

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

Перевірити виконання достатньої умови збіжності.

4 Переконатися в тім, що якщо A - нижня трикутна матриця, з ненульовими діагональними елементами, то метод Зейделя збігається за одну ітерацію.

5 Переконатися в тім, що якщо A - діагональна матриця з ненульовими діагональними елементами, то метод Зейделя збігається за одну ітерацію.

6 Переконатися в тім, що якщо A - верхня трикутна матриця, з ненульовими діагональними елементами, то метод Зейделя збігається за скінченне число ітерацій. Знайти цю кількість ітерацій.

7 При яких значеннях і метод простої ітерації, застосований для розв’язання системи з і деяким вектором , збігається?

8 Нехай система розв’язується методом Якобі , n =0,1,…... Показати, що достатня умова збіжності методу (при й ) еквівалентна умові діагональної переваги матриці .

У задачах 9-13 передбачається, що ітераційні методи розв’язання системи записані в канонічній формі , n=0,1,…, де й - ітераційні параметри.

9 Нехай всі власні значення матриці A дійсні й додатні. Довести збіжність методу при з будь-якою матричною нормою.

10 Нехай A - матриця простої структури й всі власні числа , m >0. Довести, що ітераційний метод із задачі 9 збігається при .

11 Довести, що для систем 2-го порядку метод простої ітерації (метод Якобі)

і метод Зейделя:

збігаються і розбігаються одночасно. Тут , -діагональна матриця, - нижня трикутна матриця, - верхня трикутна матриця.

12 Довести, що для методу Зейделя необхідною й достатньою умовою збіжності є така умова: всі корені рівняння

за модулем повинні бути менше 1. Тут , – елементи матриці вихідної системи .

13 Довести, що якщо , то справедлива оцінка

, , де й - мінімальне й максимальне власні значення матриці .

Розділ 4

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

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

(4.1)

Представимо цю систему в матричному вигляді

, (4.2)

де , .

Очевидно, для нелінійного рівняння (4.2) можна застосувати підходи, викладені в розділі 2 нашої книги, а саме там йшлося про ітераційні методи отримання наближень до кореня для нелінійних рівнянь, визначених на множинах довільної природи. Тут же йдеться про розв’язок на множині елементів з . Розглянемо особливості застосування ітераційних методів для розв’язання систем нелінійних алгебраїчних рівнянь (СНАР).

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

Нехай система нелінійних рівнянь (4.2) приведена до спеціального вигляду , де функції дійсні, визначені і неперервні в деякій області ізольованого розв’язку цієї системи.

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

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

Якщо R – сукупність векторів , для яких , то в R є єдиний розв’язок. Розглянемо матриці

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

При виконанні умов збіжності ітераційного процесу для розв’язання системи нелінійних рівнянь можна застосовувати аналог методу Зейделя:

Теорема 1 Нехай область G замкнена і відображення є стискаючим у G, тобто виконана умова . Тоді, якщо для ітераційного процесу всі послідовні наближення x^(p)є G, то:

1) незалежно від вибору початкового наближення ітераційний процес збігається, тобто існує

при ;

2) граничний вектор x^* є єдиним розв’язком рівняння в G;

3) справедлива оцінка .

Теорема 2 Нехай і неперервні в області G, причому в G виконується нерівність

.

Якщо послідовні наближення

не виходять з G, то процес ітерації збігається і граничний вектор при є в G єдиним розв’язком.

4.2 Ітераційний метод Ньютона для СНАР

Нехай, керуючись підходами, викладеними в розділі 2, знайдено p -е наближення

одного з ізольованих коренів векторного рівняння (4.2). Тоді точний корінь можна подати у вигляді

, (4.3)

де - похибка кореня.

Підставимо (4.3) у (4.2):

. (4.4)

Нехай – неперервна диференційована функція в деякій опуклій області, що містить і , розкладемо ліву частину (4.4) в ряд за степеням малого вектора , обмежившись лінійними членами:

(4.5)

З (4.5) випливає, що під треба розуміти матрицю Якобі системи функцій f₁, f₂,…,f_n щодо x₁,x₂,…,x_n

Система (4.5) являє собою систему лінійних рівнянь відносно похибок (i=1,2,…,n) з матрицею W(x), тому формула (4.5) набере вигляду

_.

Допускаючи, що W(x)– невироджена, знаходимо

,

значить,

. (4.6)

Отримали інтерполяційну формулу Ньютона для СНАР. Очевидно, формула (4.6) дозволить побудувати збіжну до кореня ітераційну послідовність за умови, що відображення буде стискаючим. Для цього треба правильно обрати нульове наближення .

Теорема 3. Маємо нелінійну систему рівнянь з дійсними коефіцієнтами (4.2), де вектор-функція визначена і неперервна разом зі своїми частковими похідними 1-го і 2-го порядків в області w. Вважатимемо, що є точка, яка лежить у w разом зі своїм замкненим -околом. Причому виконані умови:

1) Матриця Якобі при = має обернену Г₀, де ||Г₀||<=A₀, (в змісті m-норми)

2) ||Г₀f(x⁰)||<=B₀<=H/2

3) <=C при i,j=1,2,…,n

4) постійні A₀, B₀ і C задовольняють нерівність m₀=2n₀B₀C<=1

Тоді процес Ньютона (4.6) при початковому наближенні збігається і граничний вектор

є розв’язком системи таким, що ||x*-x⁰||<=2B₀<=H.

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

При побудові процесу Ньютона (4.6) істотною незручністю є необхідність для кожного кроку заново обчислювати обернену матрицю Якобі. Якщо ця матриця неперервна в околі шуканого розв’язку x⁰, досить близького до x^*, то приблизно можна покласти

і ми приходимо до модифікованого методу Ньютона

.

4.4 Метод градієнтного спуску

Припустимо, що в системі нелінійних алгебраїчних рівнянь (4.2) функції f_i дійсні і неперервно диференційовані в їхній загальній області визначення. Розглянемо функцію

. (4.7)

Очевидно, що кожен розв’язок системи (4.2) перетворює в нуль функцію U(x); і навпаки, числа x₁,x₂,...,x_n, для яких функція U(x) дорівнює нулю, є коренем системи (4.2).

Припустимо, що система має лише ізольований розв’язок, що являє собою точку строгого мінімуму функції U(x) у n -вимірному просторі ={x₁,x₂,..., x_n }.

Нехай - корінь системи (4.2) і - його нульове наближення. Через точку проведемо поверхню рівня функції U(). Якщо точка досить близька до кореня , то при наших припущеннях поверхня рівня U()=U( ) буде схожа на еліпсоїд.

З точки рухаємося по нормалі до поверхні U()=U( ) доти, поки ця нормаль не доторкнеться в деякій точці іншої поверхні рівня U()= U( ).

Потім, відправляючись від точки , знову рухаємося по нормалі до поверхні рівня U()= U( ) доти, поки ця нормаль не доторкнеться в деякій точці нової поверхні рівня U()= U( ), і т.д.

Оскільки U( )>U( )>U( )>..., то, рухаючись таким чином, ми швидко наближаємося до точки з найменшим значенням U ("дно ями"), що відповідає кореневі системи (4.2). Позначимо через

градієнт функції U(). Визначимо описаний алгоритм пошуку точок-наближень за формулою

. (4.8)

Залишається визначити множники l_p. Для цього розглянемо скалярну функцію .

Функція F(l) дає зміну рівня функції U уздовж відповідної нормалі до поверхні рівня в точці . Множник l=l_p потрібно вибрати таким, щоб F(l) мала мінімум. Керуючись необхідною умовою екстремуму функції, одержуємо рівняння

. (4.9)

Найменший додатний корінь цього рівняння і дасть нам значення l_p. Будемо вважати, що l - мала величина, квадратом і вищими ступенями якої можна зневажити. Маємо . Розкладаючи функції f_i за степенями l з точністю до лінійних членів, одержимо

,

де . Звідси

Отже, ,

де - матриця Якобі. Далі маємо

.

Звідси ,

де W`(x) - транспонована матриця Якобі. Тому остаточно , а . Отримали розрахункову формулу методу градієнтного спуску з визначенням кроку.

Сучасна комп’ютерна техніка дозволяє суттєво спростити цей метод розв’язання нелінійних систем. Множник l_p у формулі (4.8) обирають як достатньо малий постійний крок у напрямку антиградієнта. Наприклад, l_p=0.00001.

Приклад. Розв’язати систему нелінійних рівнянь з точністю e=0,0001

Скористаємося методом градієнтного спуску. Для цього побудуємо функцію , де , а .

Кожен розв’язок системи - це нуль функції і навпаки. Виберемо початкове наближення . Позначимо Пошук розв’язку проводимо за формулою

.

Множник l(p) визначається так: , де:

.

Тоді процес здійснюється за формулою

;

W – матрица Якобі: .

Пошук наближень до розв’язку припиняється за умови .

Реалізація алгоритму на псевдокоді:

VectorF(F,x):

//розраховуємо коефіцієнти вектора F при x

end

VectorW(W,x):

//розраховуємо коефіціенти матриці W при x

end

//W – матриця Якобі

//F – матриця системи

//Z – результат множення

multWF(W,F,Z): // множення W на F

15 for i:=1 to W.lengthI do

16 for j:=1 to W.lengthJ do

17 Z[i]+=W[i,j]*F[j]

Done

Done

End

//A – вихідна матриця

//X – транспонована матриця

Transpon(A,X):

1 for i:=1 to A.lengthI do

2 for j:=1 to A.lengthJ do

3 if i=j then

4 X[i,j]:=A[i,j]

Else

6 X[i,j]:=A[j,i]

Fi

Done

Done

End

Scalar(A,B): //скалярний добуток векторів a та b

1 s:=0

2 for i:=1 to A.length do

3 s+=A[i]*B[i]

Done

5 return s

end

// розв’язання нелінійної системи методом градієнтного спуску

Solve_NonLinear_System(F,W,X):

1 n:=A.lengthI

2 for i:=1 to n do

3 X[i]:=-1;

Done

5 k:=0

Repeat

7 k++

8 for i:=1 to n do

9 XK[i]:=X[i]

Done

11 Vectorf(F,xk)

12 MatrixW(W,xk)

13 MultWF(wt,f,u)

14 MultWF(w,u,z)

15 mu:=(scalar(f,z))/(scalar(z,z))

16 maxr:=0

17 for i:=1 to n do

18 X[i]:=XK[i]-mu*U[i]

19 if abs(X[i]-XK[i])>maxr then

20 maxr:=abs(X[i]-XK[i])

Fi

22 until maxr<eps

Done

end.

Відповідь: X=0.50, Y=1.00, Z=1.00.

4.5 Метод релаксацій

Перепишемо систему (4.1) у вигляді

= + ,

де - деяка константа, і побудуємо ітераційний процес за схемою

^(k+1) = ^(k) + .

Параметр повинен бути таким, щоб в околі pозв’язку виконувалася достатня умова збіжності

|| Е + W || < 1,

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

|| ^(k)- ^(k-1)||<|| ^(k-1)- ^(k-2)||.

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

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

використовуючи метод Ньютона для системи нелінійних рівнянь. Знайти корінь за допомогою убудованого блоку розв’язку рівнянь Given Find пакета MATHCAD. Рівняння системи:

.

Локалізація кореня

Перше рівняння, визначене відносно x2: . Друге рівняння, визначене відносно x2: .

Маємо .

Перший корінь

Початкове наближення: .

Точність для блоку Given Find: TOL:= .

Розв’язання системи f(x1,x2)=0 за допомогою убудованого блоку MATHCAD:

Given

0

0

Find(

Отриманий наближений розв’язок .

Питання і завдання до розділу 4

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

2 Метод простої ітерації: опис методу, умова й швидкість збіжності, критерій закінчення, приведення до вигляду, зручного для ітерацій.

3 Метод Ньютона: опис методу, теорема про збіжність, критерій закінчення.

4 Недоліки методу Ньютона. Модифікації методу Ньютона.

5 Застосування методів розв’язання систем нелінійних рівнянь для задачі мінімізації функцій.

6 Розв’язати методом Ньютона з точністю системи рівнянь:

a) , ;

b) , .

7 Чи можна стверджувати, що система має, й до того ж єдиний, розв’язок?

8 Для системи рівнянь виписати розрахункові формули методу релаксацій:

9 Розв’язати методом простої ітерації такі системи:

a) , ;

b) , .

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

Розділ 5

Апроксимація функцій

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

5.1 Поняття про наближення функцій

Нехай величина у є функцією аргумента х. Це означає, що будь-якому значенню х з області визначення поставлено у відповідність значення у. Разом з тим на практиці часто невідомий явний зв'язок між у та х, тобто неможливо записати цей зв'язок у вигляді деякої залежності y=f(x). У деяких випадках навіть при відомій залежності y=f(x) вона настільки громіздка (наприклад, містить вирази, що важко обчислюються, складні інтеграли і т.п.), що її використовувати в практичних розрахунках важко.

Найбільш поширеним і практично важливим випадком, коли вигляд зв'язку між параметрами х та у невідомий, є його завдання у вигляді деякої таблиці {x_i, y_i}. Це означає, що дискретній множині значень аргумента {x_i} поставлена у відповідність множина значень функції {y_i} (i=0,1,…,n). Ці значення - або результати розрахунків, або експериментальні дані. На практиці нам можуть знадобитися значення величини у і в інших точках поза вузлами x_i. Однак одержати ці значення можна лише шляхом дуже складних розрахунків або проведенням дорогих експериментів.

Таким чином, з огляду економії часу і засобів ми приходимо до необхідності використання наявних табличних даних для наближеного обчислення невідомого параметра у при будь-якому значенні (з деякої області) визначального параметра х, оскільки точний зв'язок y = f(x) - невідомий.

Цій меті підпорядкована задача про наближення (апроксимацію) функцій: задану функцію f(x) потрібно приблизно замінити (апроксимувати) деякою функцією F(x) так, щоб відхилення (у деякому змісті) F(x) від f(x) у заданій області було найменшим. Функція F(x) при цьому називається апроксимуючою.

Апроксимуючими функціями можуть бути поліноміальні, тригонометричні, експонентні та ін.

Якщо наближення будується на заданій дискретній множині точок {x_i}, то апроксимація називається точковою. До неї належать інтерполяція, середньоквадратичне наближення та ін. При побудові наближення на неперервній множині точок (наприклад, на відрізку [a,b]) апроксимація називається неперервною (або інтегральною).

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

5.2 Iнтерполювання функції

Загальна постановка задачі інтерполювання така. Задані значення функції аргумента при відповідних його значеннях . Побудувати неперервну функцію , що належить до заданого класу функцій, таку, що вона збігається з при значеннях аргумента . Така функція називається інтерполюючою. Точки x_i, i=1,…,n називаються вузлами інтерполяції і вони утворюють сітку розбиття ,а y_i - вузловими значеннями.

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

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

. (5.1)

Тепер задача інтерполювання звелася до пошуку значень невідомих коефіцієнтів полінома (5.1) з умови набуття ним значень при значеннях аргумента .

Існують кілька способів визначення цих коефіцієнтів. Вони відрізняються методикою обчислень, зручною в одних і незручною в інших випадках. Але при ідеальних обчисленнях вони, природно, призводять до тих самих результатів, тобто до того самого полінома.