Історія чисельних методів.

Історія чисельних методів.

Можна виділити три основні періоди.

Перший почався (3 ÷ 4) тисячі років назад. Він був пов’язаний з веденням конторських книг, обчисленням площ, об’ємів, розрахунком найпростіших механізмів. Чисельними засобами служили спочатку власні пальці, а потім – рахівниці. Вхідні дані містили мало цифр, більшість викладок виконувалось точно, без заокруглень.

Другий почався з Ньютона. В цей період вирішувались задачі астрономії, геодезії, розрахунку механічних конструкцій. Вони зводились або до алгебраїчних систем з великим числом невідомих, або до звичайних диференціальних рівнянь. Обчислення виконувались із заокругленням; часто від результату вимагалась висока точність, доводилось зберігати до 8 значущих цифр.

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

Третій період почався приблизно з 1940р. Військові задачі, наприклад, наводка зенітних гармат на швидкісний літак – вимагали від людини швидкості і призвели до розробки електричних систем. З’явились ЕОМ. Їх швидкодія настільки перевищувала швидкодію механічних засобів, що стало можливим проводити обчислення великого об’єму. Це дозволило чисельно вирішувати нові класи задач. Спочатку використовувались чисельні методи, які були розробленні в “доелектронному” періоді. Але застосування ЕОМ привело до переоцінки методів. Багато старих методів виявилось непридатними для автоматизованих обчислень. Почали скоро розроблятися нові методи, орієнтовані прямо на ЕОМ.

Чисельні методи – методи наближеного або точного рішення задач чистої або прикладної математики, що базуються на побудові скінченної послідовності дій над скінченою множиною чисел.

При рішенні задач прикладної математики найбільш ефективною вважають таку методологію. По-перше складають математичну модель. Її формулюють звичайно в термінах інтегральних і диференціальних рівнянь функцій неперервного аргументу. Це так звана континуальна математична модель. По-друге здійснюють перехід від континуальної математичної моделі до дискретної математичної моделі. Цей перехід полягає в заміні функції неперервного аргументу функціями дискретного аргументу, а рівняння континуальної математичної моделі – зазвичай різницевими рівняннями. При цьому інтеграл замінюють кінцевою сумою, а похідну – різницевим відношенням. Внаслідок цього приходять, як правило, до системи з великою кількістю рівнянь з багатьма невідомими (дискретна математична модель). По-третє складають обчислювальний алгоритм (ОА) для рішення одержаної системи рівнянь з деякою певною точністю. По-четверте здійснюють програмування.

Перехід від континуальної до дискретної математичної моделі приводить до появи похибки апроксимації. При практичних розрахунках необхідно враховувати і похибку заокруглення внаслідок обмеженої кількості значущих цифр при операціях в ЕОМ над машинними числами. Враховуючи це одержують реальний ОА. Це привело до необхідності проводити аналіз похибок і гарантовану оцінку точності реальних обчислень.

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

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

Система параметрів називається мінімальною для наближеного аргументу, якщо відмова від будь-якої з них порушує властивість збіжності.

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

Похибки по різному впливають на хід обчислення. Одні похибки зменшуються і при цьому не складають серйозних труднощів, а другі можуть зростати настільки сильно, що обчислення може виявитися непотрібним. Стійкість чисельного методу залежить від швидкості росту таких похибок. Чи будуть малі вихідні похибки породжувати невеликі похибки результатів? Якщо так, то метод стійкий; однак якщо навіть малі вихідні похибки надають згубну дію на результат, то метод виявляється нестійким.

 

Похибки обчислень.

Заокруглення чисел.

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

Правила округлення за доповненням.

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

При цьому:

1) якщо перша з відкинутих цифр менша 5-ти, то залишені десяткові знаки зберігаються без змін;

2) якщо перша з відкинутих цифр бульша 5-ти, то до останньої залишеної цифри додається одиниця;

3) якщо перша з відкинутих цифр дорівнює 5-ти, та серед решти відкинутих цифр є ненульові, то остання залишена цифра збільшується на одиницю;

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

 

Похибка обчислення функції.

Нехай відомі похибки деякої системи величин. Потрібно визначити похибку даної функції від цих величин.

Нехай задана диференційованана функція

u = f (x₁, x₂, … , x_n)

і нехай │Δx_і│ (і = 1, 2, … , n) абсолютна похибка аргументів функції. Тоді абсолютна похибка функції

Як правило, на практиці │Δx_і│ настільки мала величина, що добутками, квадратами і вищими степенями можна знехтувати. Тому можна покласти

Тут повний приріст замінюємо повним диференціалом, отже

                                   (1)

Позначивши через Δx_і  (і = 1, 2, … , n) граничні абсолютні похибки аргументів x_і, а через Δu – граничну похибку функції і для малих Δx_і одержимо

– гранична абсолютна похибка функції                 (2)

Поділивши обидві частини нерівності (1) на │u│, одержимо оцінку для відносної похибки функції u

Тоді гранична відносна похибка

Наприклад, для двох змінних

 

 

Похибка суми.

Теорема 1.

Абсолютна похибка алгебраїчної суми декількох наближених чисел не перевищує суми абсолютних похибок цих чисел.

                          (1)

Гранична абсолютна похибка суми дорівнює сумі граничних абсолютних похибок доданків

                                 (2)

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

Практичне правило для додавання наближених чисел. Щоб додати числа різної абсолютної точності необхідно:

1) Виділити числа, десятковий запис яких обривається раніше інших, (тобто числа, що мають найменшу абсолютну точність), і залишити їх без змін;

2) Числа, які залишилися, необхідно заокруглити по взірцю виділених, зберігаючи один або два запасних десяткових знаки;

3) Додати дані числа, враховуючи всі збережені знаки;

4) Одержаний результат заокруглити на один знак.

Теорема 2.

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

Нехай , причому приймаємо, що х_і > 0 (i = 1, 2, …, n).

Гранична відносна похибка

;

Нехай  найбільша із граничних відносних похибок доданків , тобто < . Тоді

Отже , тобто .

 

Похибка різниці.

Розглянемо різницю двох наближених чисел

За формулою для граничної абсолютної похибки алгебраїчної суми одержимо

тобто абсолютна похибка різниці оцінюється так само, як і для суми.

Гранична абсолютна похибка різниці дорівнює сумі граничних абсолютних похибок зменшуваного і від’ємника.

Звідси гранична відносна похибка різниці:

                                            (1)

Якщо наближені числа х₁ і х₂ достатньо близькі один до одного, то різниця мала. З формули (1) випливає, що гранична відносна похибка в цьому випадку може бути досить великою, в той час коли відносна похибка зменшуваного і від’ємника залишається малою, тобто тут відбувається втрата точності. Звідси випливає практичне правило: при наближених обчисленнях слід по можливості уникати віднімання двох рівних близьких чисел; якщо в силу необхідності доводиться віднімати такі числа, то слід зменшуване і від’ємник брати з достатнім числом запасних знаків (якщо існує така можливість). Наприклад, якщо відомо, що при відніманні чисел х₁ і х₂ перші m значущих цифр зникнуть, то слід брати х₁ і х₂ з (m + n) вірними значущими цифрами.

Приклад. Знайти різницю  з трьома правильними знаками.

Оскільки                            ,

то результат                          u = 0,00353 = 3,53∙10^{– 3}.

Цей результат можна отримати, якщо записати u у такому вигляді (перетворимо вираз, щоб уникнути віднімання двох близьких чисел)

і взяти корені лише з трьома правильними знаками

.

 

Похибка добутку.

Теорема.

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

покладемо  , одержимо δ ≤ δ₁ + δ₂ +…+ δ_n .

Формула правильна, якщо співмножники мають однакові або різницеві знаки.

Наприклад,                   u = x₁ · x₂

                                  ln u = ln x₁ + ln x₂ ,

        

Наслідок. Гранична відносна похибка добутку дорівнює сумі граничних відносних похибок співмножників, тобто

Розглянемо частковий випадок

u = k · x , де k – точний множник, відмінний від нуля.

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

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

1) заокруглити їх так, щоб кожне з них мало на одну (або дві) значущих цифри більшу, ніж число правильних цифр в найбільш точному із співмножників;

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

 

Похибка частки

Теорема:

Відносна похибка частки не перевищує суми відносних похибок діленого і дільника.

Нехай    Тоді на основі   одержимо

.

Наслідок. Якщо   то

Нехай ділене х₁ і дільник х₂ мають щонайменше m вірних цифр. Якщо α і β їх перші значущі цифри, то за граничну відносну похибку частки u може бути прийнята величина

Звідси одержимо правило:

1) якщо α ≥ 2 і β ≥ 2, то частка u має щонайменше (m – 1) вірних знаків;

2) якщо α = 1 і β = 1, то частка u має (m – 2) вірних знаків.

Відносна похибка степеня.

Нехай  (де m – натуральне число). Тоді

 , де δ′ – відносна похибка числа

і                              ,

тобто гранична відносна похибка т-го степеня числа в т разів більша граничної відносної похибки самого числа.

 

Поняття про матриці.

Система чисел розташованих в прямокутній таблиці із “ т ” рядків та “ n ” стовпців називається матрицею розміру т  n.

                                   (1)

Числа а _ij , де   i – номер рядка; j – номер стовпця – називають елементами матриці. Для матриці часто використовують скорочену форму запису

( ; )

або                              

Якщо матриця складається з одного рядка (тобто має порядок 1  n), то вона називається вектором-рядком

Якщо ж матриця складається з одного стовпця (т  1 – порядку) – вона називається вектором-стовпцем.

Якщо число рядків і стовпців однакове, то матриця називається квадратною (тобто т = n). Якщо т ≠ n, то – прямокутною. Число (скаляр) можна розглядати як матрицю 1 1.

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

Квадратна матриця вигляду

                                     (2)

називається діагональною матрицею. Якщо при цьому α_і = 1 , то матриця (2) називається одиничною і позначається буквою Е, тобто

Матриця, всі елементи якої рівні нулю, називають нульовою і позначається через нуль. При необхідності вказати число рядків і стовпців використовують позначення 0_mn .

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

А = В            а _ij = b_ij

 

Добуток матриць.

Нехай А та В матриці порядків т  n та n  р відповідно. Добуток матриць

це матриця С розміру т  р.

( ; )

Правило множення: щоб одержати елемент , що стоїть в і – му рядку та j – му стовпці добутку двох матриць, необхідно елементи і – го рядка першої матриці помножити на відповідні елементи j – го стовпця другої матриці і одержані добутки додати.

Слід наголосити, що множення А на В допустиме (тобто добуток А ∙ В існує), якщо число стовпців А дорівнює числу рядків В.

Приклад.

 .

Якщо в матриці т  n

замінити рядки власними стовпчиками, то одержимо матрицю

розміру n  т, котра називається транспонованою по відношенню до матриці А. Для вектора-рядка транспонованою матрицею є вектор-стовпчик.

 

Метод послідовних наближень (метод Пікара).

Нехай задано рівняння

або                                                                                  (1)

права частина якого в прямокутнику  неперервна та має неперервну частинну похідну по у. Потрібно знайти розв’язок рівняння (1), що задовольняє початковій умові

х = х₀ , у(х₀) = у₀                                            (2)

Інтегруючи обидві частини рівняння від х₀ до х, одержимо:

або                                                                   (3)

Рівняння (1) заміняється інтегральним рівнянням (3). Інтегральне рівняння (3) задовольняє диференціальне рівняння (1) і початковій умові (2). Дійсно

Замінюючи в рівності (3) функцію у значенням у₀, одержимо перше наближення

                             (4)

Одержуємо послідовність функцій { у_і (х) }, що збігається до функції у (х), яка є розв’язком диференціального рівняння у′ = f ( х, у )

у₁ (х), у₂ (х), у₃ (х), …, у _n (х)

Приклад.

Розв’язати методом Пікара диференціальне рівняння у′ = х² + у² . Початкові умови х₀ = 0, у(х₀)= = у₀ = 0.

Переходимо до інтегрального рівняння

,

або з врахуванням початкових умов

Одержимо послідовні наближення

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

 

Історія чисельних методів.

Можна виділити три основні періоди.

Перший почався (3 ÷ 4) тисячі років назад. Він був пов’язаний з веденням конторських книг, обчисленням площ, об’ємів, розрахунком найпростіших механізмів. Чисельними засобами служили спочатку власні пальці, а потім – рахівниці. Вхідні дані містили мало цифр, більшість викладок виконувалось точно, без заокруглень.

Другий почався з Ньютона. В цей період вирішувались задачі астрономії, геодезії, розрахунку механічних конструкцій. Вони зводились або до алгебраїчних систем з великим числом невідомих, або до звичайних диференціальних рівнянь. Обчислення виконувались із заокругленням; часто від результату вимагалась висока точність, доводилось зберігати до 8 значущих цифр.

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

Третій період почався приблизно з 1940р. Військові задачі, наприклад, наводка зенітних гармат на швидкісний літак – вимагали від людини швидкості і призвели до розробки електричних систем. З’явились ЕОМ. Їх швидкодія настільки перевищувала швидкодію механічних засобів, що стало можливим проводити обчислення великого об’єму. Це дозволило чисельно вирішувати нові класи задач. Спочатку використовувались чисельні методи, які були розробленні в “доелектронному” періоді. Але застосування ЕОМ привело до переоцінки методів. Багато старих методів виявилось непридатними для автоматизованих обчислень. Почали скоро розроблятися нові методи, орієнтовані прямо на ЕОМ.

Чисельні методи – методи наближеного або точного рішення задач чистої або прикладної математики, що базуються на побудові скінченної послідовності дій над скінченою множиною чисел.

При рішенні задач прикладної математики найбільш ефективною вважають таку методологію. По-перше складають математичну модель. Її формулюють звичайно в термінах інтегральних і диференціальних рівнянь функцій неперервного аргументу. Це так звана континуальна математична модель. По-друге здійснюють перехід від континуальної математичної моделі до дискретної математичної моделі. Цей перехід полягає в заміні функції неперервного аргументу функціями дискретного аргументу, а рівняння континуальної математичної моделі – зазвичай різницевими рівняннями. При цьому інтеграл замінюють кінцевою сумою, а похідну – різницевим відношенням. Внаслідок цього приходять, як правило, до системи з великою кількістю рівнянь з багатьма невідомими (дискретна математична модель). По-третє складають обчислювальний алгоритм (ОА) для рішення одержаної системи рівнянь з деякою певною точністю. По-четверте здійснюють програмування.

Перехід від континуальної до дискретної математичної моделі приводить до появи похибки апроксимації. При практичних розрахунках необхідно враховувати і похибку заокруглення внаслідок обмеженої кількості значущих цифр при операціях в ЕОМ над машинними числами. Враховуючи це одержують реальний ОА. Це привело до необхідності проводити аналіз похибок і гарантовану оцінку точності реальних обчислень.

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

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

Система параметрів називається мінімальною для наближеного аргументу, якщо відмова від будь-якої з них порушує властивість збіжності.

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

Похибки по різному впливають на хід обчислення. Одні похибки зменшуються і при цьому не складають серйозних труднощів, а другі можуть зростати настільки сильно, що обчислення може виявитися непотрібним. Стійкість чисельного методу залежить від швидкості росту таких похибок. Чи будуть малі вихідні похибки породжувати невеликі похибки результатів? Якщо так, то метод стійкий; однак якщо навіть малі вихідні похибки надають згубну дію на результат, то метод виявляється нестійким.

 

12345Следующая ⇒

Поделиться: