Числові методи

Числові методи

(реферат)

Вступ

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

Метричні простори. Теорема Банаха

Множина елементів однакової природи називається простором, якщо на ній встановлені просторово схожі відношення між її елементами.

Простір М називається метричним простором, якщо кожній парі x, y M ставиться у відповідність число (x, y), яке називається віддаллю (або метрикою) і яке задовольняє аксіомам метрики, а саме:

(x, y)0, причому (x, y)=0 лише для x=y;

(x, y)= (y, x); (1.1)

(x, y) (x, z)+ (z, y) (нерівність трикутника).

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

1) Множина R дійсних чисел. Точками цього простору є дійсні числа, метрикою (x, y) модуль різниці x-y,

(x, y)=x-y. (1.2)

Неважко впевнитися, що така метрика задовольняє умовам метрики (1).

2) Множина Z комплексних чисел. Точками цього простору є комплексні числа , метрикою є

(1.3)

Точка x метричного простору М називається границею послідовності елементів , якщо послідовність віддалені прямує до нуля при k:



Послідовність називається фундаментальною, якщо для будь-якого >0 знайдеться номер n такий, що при k>n і m>n. Іншими словами, послідовність фундаментальна, якщо починаючи з елемента послідовності всі наступні належать -ному точки х.

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

Нехай А відображення простору М самого на себе. Відношення А називається стискуючим, якщо існує додатне число менше за 1 (0<<1), що для будь-яких x, y M виконується нерівність

(1.4)

Точка x називається нерухомою точкою відображення А, якщо

x=А x (1.5)

Для стискаючого відображення А справедлива Теорема Банаха. Будь-яке стискаюче відображення повного метричного простору M має лише одну нерухому точку x. Послідовність , яка визначається рекурентною формулою

 (1.6)

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

(1.7)

(1.8)

Елементи (точки) називаються послідовними наближеннями до границі x. Теорема Банаха має фундаментальне значення в обчислювальній математиці для вивчення ітераційних методів розв'язування математичних задач. Приймемо теорему Банаха без доведення.

2. Лінійні простори

Множина L елементів x, y, z... називається лінійним простором, якщо для неї визначення операції додавання і множення на дійсні числа, які не виводять за межі множини L і які задовольняють таким умовам:

x+y=y+x (комутативність додавання).

(x+y)+z=x+(y+z) (асоціативність додавання).

Існує нульовий елемент L, для якого +x=x для всіх xL.

0x=0 (2.1)

(+)x=x+x

(x+y)=x+y

(x)=()x

1x=x

, - дійсні числа.

Скінчена система з k елементів лінійного простору називається лінійно незалежною, якщо рівність

лише для (так скорочено записується сукупність рівності ). В протилежному випадку система елементів є лінійно залежною системою. Максимальна кількість n лінійно незалежних елементів називається розмірностю лінійного простору. Іншими словами, якщо в просторі L існує система з n лінійно незалежних елементів, а будь-які n+1 елементів вже лінійно залежні, то n розмірність простору. Скінчена система елементів n-мірного лінійного простору L називається базисом, якщо для будь-якого елемента xL знайдеться числа такі, що

(2.2)

Досить часто базисні вектори т-мірного простору нумерують, починаючи з 1. В цьому випадку розклад по базису (2.2) запишеться у вигляді

(2.2а)

Нескінчена система елементів нескінченого лінійного простору L утворює базис, якщо для кожного елемента xL можна записати

(2.3)

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

Лінійний простір L називається нормованим, якщо кожному елементу xL можна поставити у відповідність невід'ємне число x, яке називається нормою і яке має задовільняти аксіомам норми:

x0, причому x=0 лише для x=0.

x=x. (2.4)

x+yx+z+z+y (правило трикутника).

Лінійний нормований простір стає метричним простором, якщо прийняти за метрику

x-y (2.5)

В (2.5) (x-y) різниця елементів лінійного простору, яка вводиться за правилом

x-y=x+(-1)y.

Повний лінійний нормований простір називається банаховим простором.

Лінійний простір L називається евклідовим, якщо кожній парі x, yL можна поставити у відповідність дійсне число (x, y) або xy, яке називається скалярним добутком і яке задовільняє таким умовам

xx0, причому xx=0 лише для x=0.

xy=yx. (2.6)

(x)y=(xy).

(x+y)z=xz+yz.

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

Гільбертовий простір є банаховим, тому що в ньому можна ввести норму за правилом

(2.7)

З використанням скалярного добутку необхідна і достатня умова лінійної незалежності векторів в гільбертовому просторі формулюється як відмінність від нуля визначника Грама

(2.8)

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

Якщо , то вектор називається нормованим. Скінчена або нескінчена система векторів є ортогональною, якщо її елементи попарно ортогональні між собою, тобто

, якщо ik.

Якщо вектори ортогональної системи векторів нормовані, , то система векторів ортонормована. Тобто, система векторів ортонормована, якщо

3. Простір R⁽ⁿ⁾ n-мірних векторів

Множина векторів

t - індекс транспонування (так для економії місця позначаються вектори, які звично записуються в стовпчик), якщо операції додавання векторів та множення на дійсні числа ввести за такими правилами:

(3.1)

Легко впевнитися, що аксіоми метричного простору (2.1) виконуються. Розмірність цього простору дорівнює n. Система векторів:

(3.2)

......................................................

- символ Кроткера, дорівнює 1, якщо i=j і 0, якщо ij) утворює канонічний (тобто найпростіший) базис. Дійсно, для будь-якого вектора можна записати

(3.3)

нульовим елементом простору R⁽ⁿ⁾ є вектор

,

в якого всі елементи дорівнюють нулю.

Простір R⁽ⁿ⁾ стає нормованим, якщо для кожного вектора ввести норму за правилом

- евклідова норма (3.3а)

Або

, (3.3б)

Або

, (3.3в)

або ще багатьма іншими способами.

Геометричний зміст цих норм легко можна побачити на прикладі двовимірних векторів (мал. 1).

Простір R⁽ⁿ⁾ стає евклідовим, якщо ввести скалярний добуток за правилом

(3.4)

Простір R⁽ⁿ⁾ є гільбертовим, а значить і банаховим.

4. Простір R^(nхn) квадратних матриць

Множина матриць з дійсними елементами

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

(4.1)

Легко можна впевнитися, що умови (8) при цьому задовільняються. Розмірність цього простору nxn. Канонічний базис утворюють матриці

,

в яких лише один елемент дорівнює 1, а всі решту 0. Наприклад, матриця

,

а матриця

.

Простір R⁽ⁿ⁾ стає нормованим, якщо для матриці ввести норму за правилом

- евклідова норма (4.2а)

або

(4.2б)

або

(4.2в)

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

;

;

.

Норма матриці є узгодженою з нормою вектора , якщо виконується нерівність

(4.3)

Можна довести, що евклідова норма матриці узгоджена з евклідовою нормою вектора , аналогічно узгодженими є норми і та і . Простір R^(nхn) є банаховим простором.

5. Наближені числа

Нехай наближене число до точного числа а. Різниця

(5.1)

називається похибкою наближеного числа . Модуль похибки

(5.2)

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

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

, (5.3)

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

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

(5.4)

або в скороченій формі:

(5.5)

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

, (5.6)

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

. (5.7)

Нехай для визначеності >0, а >0. Тоді

.

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

(5.8)

Аналогічно,

і (5.9)

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

і (5.8а)

(5.9а)

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

Нехай наближене число записане у вигляді скінченого десяткового дробу:

де - цифри числа .

Значущими цифрами числа називають всі праві цифри відносно першої ненульової цифри. Наприклад, в числах =0.0503 і =0.00630500 значущі цифри підкреслені, непідкреслені нулі записуються для позначення розрядів. Значуща цифра називається вірною значущою цифрою, якщо гранична абсолютна похибка не перевищує 10^k (не перевищує одиниці k-го розряду числа), в протилежному випадку цифра - сумнівна. Наприклад, в числі =0.0503 з абсолютною похибкою =0.00002 вірними є всі значущі цифри, а в числі =0.00630500 з =0.000008 вірними є лише три підкреслені значущі цифри, решту - сумнівними.

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

Якщо крім 5 серед відкинутих цифр є відмінні від нуля значущі цифри.

Якщо серед відкинутих цифр лише одна 5 є значущою відміною від нуля і остання залишена цифра є непарною.

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

4.37844.38 перша відкинута цифра (підкреслені відкинуті цифри) більша 5.

4.37494.37 перша відкинута цифра менша 5.

4.375014.38 перша відкинута цифра 5 і після неї є ненульові значущі цифри.

4.3754.38 перша відкинута цифра 5, після неї немає ненульових значущих цифр і остання залишена

цифра непарна.

4.3654.36 перша відкинута цифра 5, після неї немає ненульових значущих цифр і остання залишена цифра парна.

За пропозицією академіка А.Н. Крилова наближені числа необхідно записувати так, щоб в них всі значущі цифри, крім останньої, були вірними і лише остання цифра - сумнівна, причому величина граничної абсолютної похибки не перевищує половини одиниці останнього збереженого розряду. Якщо наближені числа не мають остаточного характеру, то в них необхідно зберігати одну або дві сумнівні цифри. За цим правилом число =7.48 має граничну абсолютну похибку =0.005.

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

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

.

Допускаючи, що достатньо малі, можна наближено поставити

.

З останньої рівності можна зробити висновок, що

(5.10)

Для відносної похибки можна записати

.

Звідси випливає, що

. (5.11)

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

Похибка суми. , . З (5.10) випливає

, (5.12)

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

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

(5.12а)

Для граничної відносної похибки можна одержати

, (5.13)

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

Дійсно, нехай А₁ - точне значення x₁, А₂ - точне значення x₂, і т.д.

Тоді

,

де А=А₁+А₂+...+А_n - точне значення суми.

Враховуючи, що з останньої рівності випливає, що

,

де .

Похибка різниці. , і з (5.10) одержується

, (5.14)

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

Для граничної відносної похибки різниці можна записати

, (5.15)

де А - точне значення різниці. Якщо наближені числа x₁ і x₂ досить близькі одне до одного і мають малі граничні абсолютні похибки, то А мале, а гранична відносна похибка може бути досить великою. Таке явище називається втратою точності. Для прикладу, нехай x₁=47.132 і x₂=47.111, кожне з яких має по 5 вірних значущих цифр. Різниця чисел =0.021 має лише дві значущі цифри, друга з яких сумнівна, тому що гранична абсолютна похибка y=0.0005+0.0005=0.001.

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

(при малих b).

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

Приклад цього. Необхідно знайти різницю

.

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

і обчислити корені із 3 вірними знаками

.

При розв'язуванні задач на сучасних ПК є можливість за рахунок вибору необхідного типу даних мати необхідну кількість вірних знаків, але і в цьому випадку краще виконувати відповідні перетворення для того, щоб уникнути віднімання близьких чисел.

Похибка добутку. . При допущені, що x₁ і x₂ додатні одержується

,

і з формули (5.11) одержується

.

Остання рівність легко узагальнюється на випадок довільного числа n ?

, (5.16)

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

Похибка ділення.

. ,

і з (5.11) слідує, що

,

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

Для граничної абсолютної похибки ділення з формули (5.10) можна одержати

. (5.17)

З цієї формули випливає: якщо , то навіть при малих x₂ і x₁ гранична абсолютна похибка ділення може бути великою. Тому необхідно уникати ділення на малі числа. Приклад цього. Нехай x₁=100.0 і x₂=0.002 з граничними абсолютними похибками x₁=0.05 і x₂=0.0005. Похибка ділення

.