Визначники

Поняття визначника

Будь-якій квадратній матриці n-го порядку можна поставити у відповідність число, яке називається визначником (детермінантом) матриці A і позначається так: , або , або det A.

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

Визначник другого порядку(визначник матриці другого порядку) обчислюється так:

Мал. Схема обчислення визначника другого порядку

Отже, визначник другого порядку є сума 2=2! доданків, кожне з яких є твір 2-х співмножників – елементів матриці A, по одному з кожного рядка і кожного стовпця. Один із доданків береться зі знаком «+», інше – зі знаком «-».

Знайти визначник

Визначник третього порядку (визначник квадратної матриці третього порядку) задається рівністю:

Отже, визначник третього порядку є сума 6=3! доданків, кожне з яких є твір 3-х співмножників – елементів матриці A, по одному з кожного рядка та кожного стовпця. Одна половина доданків береться зі знаком "+", інша - зі знаком "-".

Основним методом обчислення визначника третього порядку є так зване правило «трикутників» (Правило Саррюса): перший із трьох доданків, які входять у суму зі знаком «+», є добуток елементів головної діагоналі, друге і третє – добутку елементів, що у вершинах двох трикутників з основами, паралельними головної діагоналі; три доданки, що входять у суму зі знаком «-», визначаються аналогічно, але щодо другої (побічної) діагоналі. Нижче наведено 2 схеми обчислення визначників третього порядку

б)

Мал. Схеми обчислення визначників 3 порядку

Знайти визначник:

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

Основні властивості визначників. Методи обчислення визначників

Визначники матриць мають такі основні властивості:

1. Визначник не змінюється під час транспонування матриці.

2. Якщо у визначнику поміняти місцями два рядки (або стовпці), то визначник поміняє знак.

3. Визначник із двома пропорційними (зокрема, рівними) рядками (стовпцями) дорівнює нулю.

4. Якщо у визначнику рядок (стовпець) складається з нулів, то визначник дорівнює нулю.

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

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

7. Визначник діагональної та трикутної (верхньої та нижньої) матриць дорівнює добутку діагональних елементів.

8. Визначник добутку квадратних матриць дорівнює добутку їх визначників.

Методичні вказівки для студентів І курсу

Базей Олександр Анатолійович

Одеса 2008

ЛІТЕРАТУРА

1 Хемінг Р.В. Численні методи для науковців та інженерів. - М.: Наука, 1968. - 400 с.

2 Блажко С.М. Курс сферичної астрономії. - Москва, Ленінград, ОГІЗ, 1948. - 416 с.

3 Щиголєв Б.М. Математична обробка спостережень. - М.: Наука, 1969. - 344 с.

4 Крилов В.І., Бобков В.В., Монастирний П.І. Обчислювальні методи. - М.: Наука, 1977. Том I, Том II - 400 с.

5 Худсон Д. Статистика для фізиків. - М.: Світ, 1967. - 244 с.

6. Берман Г.М. Прийоми рахунку. - Москва, 1953. - 88 с.

7.Румшинський Л.З. Математична обробка результатів експерименту. - Москва, Наука 1971. - 192 с.

8.Каліткін Н.М. Чисельні методи. - Москва, Наука 1978. - 512 с.

9. Фільчаков П.Ф. Чисельні та графічні методи прикладної математики. - Київ, "Наукова думка", 1970. - 800 с.

10. Фіхтенгольц Г.М. Курс диференціального та інтегрального обчислення, т.1-3. - Москва, Наука 1966.

Наближені обчислення 2

Про побудову графіків

Згладжування 10

Апроксимація 12

Випрямлення (лінеаризація) 13

Метод найменших квадратів 15

Інтерполювання 24

Інтерполяційний поліном Лагранжа 26

Залишковий член формули Лагранжа 29

Інтерполяційний поліном Ньютона для таблиці зі змінним кроком 30

Інтерполювання за таблицею з постійним кроком 34

Інтерполяційні поліноми Стірлінга, Бесселя, Ньютона 37

Інтерполювання за таблицею функції двох аргументів 42

Диференціювання за таблицею 44

Чисельне рішення рівнянь 46

Дихотомія (метод розподілу навпіл) 46

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

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

Пошук мінімуму функції однієї змінної 51

Метод золотого перерізу 51

Метод парабол 54

Обчислення певного інтегралу 56

Формула трапецій 59

Формула середніх або формула прямокутників 61

Формула Сімпсона 62

Вирішення звичайних диференціальних рівнянь. Завдання Коші 64

Класичний метод Ейлера 66

Уточнений метод Ейлера 67

Метод прогнозу та корекції 69

Методи Рунге-Кутта 71

Гармонійний аналіз 74

Ортогональні системи функцій 78

Метод 12 ординат 79

ПРИБЛИЖЕНИЕ ВИЛІЧЕННЯ

Вирішимо просте завдання. Допустимо, що студент живе на відстані 1247 м від вокзалу. Потяг відходить о 17 годині 38 хв. За скільки часу до відходу поїзда студент повинен вийти з дому, якщо його середня швидкість дорівнює 6 км/годину?

Рішення отримуємо відразу:

.

Однак навряд чи насправді хтось став би користуватися цим математично точним рішенням і ось чому. Обчислення виконані точно, але чи точно виміряно відстань до вокзалу? Чи можна взагалі виміряти шлях пішохода, не допустивши жодних похибок? Чи може пішохід пересуватися строго певною лінією у місті, де повно людей та автомобілів, які переміщуються у всіляких напрямках? А швидкість 6 км/година – хіба вона визначена абсолютно точно? І так далі.

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

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

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

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

Якщо кількість предметів, що перераховуються, невелика і якщо вона постійно в часі, то ми будемо отримувати абсолютно точнірезультати. Наприклад, на руці 5 пальців, у ящику 300 підшипників. Інша справа, коли кажуть: в Одесі 1979 року було 1000 000 жителів. Адже люди народжуються та вмирають, приїжджають та їдуть; число їх постійно змінюється навіть за той проміжок часу, протягом якого виконано рахунок. Тому насправді мається на увазі, що мешканців було близько 1 000 000, може бути 999125, або 1001263, або ще якесь число, близьке до 1 000 000. У цьому випадку 1 000 000 дає наближенекількість жителів міста.

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

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

Якщо ви виміряли довжину столу і отримали значення 1360.5 мм, це зовсім не означає, що довжина столу рівно 1360.5 мм – якщо цей стіл виміряє інший або ви повторите вимірювання, то можна отримати значення і 1360.4 мм, і 1360.6 мм. Число 1360.5 мм виражає довжину столу наближено.

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

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

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

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

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

2) Ці похибки, часто збільшеними, переходять у результати обчислень. Але практика і вимагає точних даних, а задовольняється результатами з деякими допустимими похибками, величина яких має бути наперед заданої.

3) Забезпечити необхідну точність результату можна лише тоді, коли вихідні дані будуть досить точними і коли враховуються усі похибки, які завдаються самими обчисленнями.

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

Зазвичай у технічних розрахунках допустимі похибки перебувають у межах від 0.1 до 5%, але у наукових питаннях може бути знижено до тисячних часток відсотка. Наприклад, при запуску першого штучного супутника Місяця (31 березня 1966 р.) стартова швидкість близько 11200 м/сек повинна була бути забезпечена з точністю до кількох сантиметрів за секунду, щоб супутник вийшов на навколомісячну, а не навколосонячну орбіту.

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

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

Використовуючи властивість визначників номер 9 0, введемо визначення визначника 4-го порядку:

приклад 2.Обчислити, використовуючи відповідне розкладання.

Аналогічно запроваджується поняття визначника 5-го, 6-го тощо. порядку. Значить визначник порядку n:

.

Усі характеристики визначників 2-го і 3-го порядків, розглянуті раніше, справедливі й у визначників n-го порядку.

Розглянемо основні методи обчислення визначників n-го порядку.

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

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

приклад 3.Обчислити приведенням до трикутного вигляду.

приклад 4.Обчислити, використовуючи спосіб ефективного зниження порядку

.

Рішення: за властивістю 4 0 визначників з першого рядка винесемо множник 10, а потім послідовно множити другий рядок на 2, на 2, на 1 і складати відповідно з першим, з третім і четвертим рядками (властивість 8 0).

.

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

Приклад 5.Обчислити визначник приведенням до трикутного вигляду.

.

приклад 3.Обчислити, використовуючи рекурентні співвідношення.

.

.

Лекція 4. Зворотня матриця. Ранг матриці.

1. Поняття зворотної матриці

Визначення 1. Квадратна матриця А порядку n називається невиродженою,якщо її визначник | A| ≠ 0. У разі, коли | A| = 0, матриця А називається виродженою.

Тільки квадратних невироджених матриць А вводиться поняття зворотної матриці А -1 .

Визначення 2 . Матриця А-1 називається зворотнійдля квадратної невиродженої матриці А, якщо А -1 А = АА -1 = Е, де Е – одинична матриця порядку n.

Визначення 3 . Матриця називається приєднаної,її елементами є додатки алгебри транспонованої матриці
.

Алгоритм обчислення зворотної матриці методом приєднаної матриці.

, де
.

Перевіряємо правильність обчислення А -1 А = АА -1 = Е. (Е – одинична матриця)

Матриці А та А -1 взаємозворотні. Якщо | A| = 0, то зворотна матриця немає.

приклад 1.Дана матриця А. Переконатися, що вона невироджена, та знайти зворотну матрицю
.

Рішення:
. Отже матриця невироджена.

Знайдемо зворотну матрицю. Складемо додатки алгебри елементів матриці А.

Отримуємо

.

Подання як вихідних даних у задачі, так і її розв'язання - у вигляді числа чи набору чисел

У системі підготовки інженерів технічних спеціальностей є важливим складником.

Основами для обчислювальних методів є:

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

Див. також

Примітки

Література

• Каліткін Н. Н. Чисельні методи. М., Наука, 1978
• Амосов А. А., Дубинський Ю. А., Копченова Н. В. "Обчислювальні методи для інженерів", 1994
• Флетчер К "Обчислювальні методи в динаміці рідин", вид. Мир, 1991 р., 504 стор.
• Є. Алексєєв «Рішення завдань обчислювальної математики в пакетах Mathcad 12, MATLAB 7, Maple 9», 2006, 496 стор.
• Тихонов А. Н., Гончарський А. В., Степанов В. В., Ягола А. Г. «Кількісні методи вирішення некоректних завдань» (1990)
• Бакушинський А. Б., Гончарський А. В. Некоректні завдання. Чисельні методи та додатки, вид. Видавництво Московського університету, 1989
• Н. Н. Каліткін, А. Б. Альшин, Є. А. Альшина, Ст Б. Рогов. Обчислення на квазірівномірних сітках. Москва, Наука, Фізматліт, 2005, 224 стор.
• Ю. Рижиков «Обчислювальні методи» вид. BHV, 2007 р., 400 стор., ISBN 978-5-9775-0137-8
• Обчислювальні методи в прикладній математиці, Міжнародний журнал, ISSN 1609-4840

Посилання

• Науковий журнал «Обчислювальні методи та програмування. Нові обчислювальні технології»

Wikimedia Foundation. 2010 .

• Обчислювальна математика та математична фізика
• Обчислювальний конвеєр

Дивитись що таке "Обчислювальні методи" в інших словниках:

Методи електроаналітичної хімії- Зміст 1 Методи електроаналітичної хімії 2 Вступ 3 Теоретична частина … Вікіпедія

Методи кодування цифрових сигналів- У цій статті не вистачає посилань на джерела інформації. Інформація має бути перевіряється, інакше вона може бути поставлена ​​під сумнів та видалена. Ви можете … Вікіпедія

ГАЗОВОЇ ДИНАМІКИ ЧИСЛІВІ МЕТОДИ- Методи вирішення завдань газової динаміки на основі обчислювальних алгоритмів. Розглянемо основні аспекти теорії чисельних методів вирішення завдань газової динаміки, записавши газову динаміку рівняння у вигляді законів збереження в інерційній… Математична енциклопедія

ДИФУЗІЙНІ МЕТОДИ- Методи вирішення кінетич. рівняння перенесення нейтронів (або інших частинок), що модифікують рівняння дифузійного наближення. Оскільки дифузійне наближення дає правильну форму асимптотич. рішення рівняння перенесення (подалі від джерел та… … Математична енциклопедія

ВОРОЖНИХ ФУНКЦІЙ МЕТОДИ МІНІМІЗАЦІЇ- чисельні способи відшукання мінімумів функцій багатьох змінних. Нехай задана обмежена знизу двічі безперервно диференційована за своїми аргументами функція для якої відомо, що при деякому векторі (знак транспонування) вона приймає ... ... Математична енциклопедія

ДЕРЖСТАНДАРТ Р 53622-2009: Інформаційні технології. Інформаційно-обчислювальні системи. Стадії та етапи життєвого циклу, види та комплектність документів– Термінологія ГОСТ Р 53622 2009: Інформаційні технології. Інформаційно-обчислювальні системи. Стадії та етапи життєвого циклу, види та комплектність документів оригінал документа: 3.1 апаратно-програмна платформа: Єдиний комплекс коштів… …

Аплікаційні обчислювальні системи- Аплікаційні обчислювальні системи, або АВС, включають системи обчислень об'єктів, засновані на комбінаторній логіці та ламбда обчисленні. Єдине, що суттєво розробляється у цих системах це уявлення про об'єкт. В… … Вікіпедія

ГОСТ 24402-88: Телеобробка даних та обчислювальні мережі. терміни та визначення- Термінологія ГОСТ 24402 88: Телеобробка даних та обчислювальні мережі. Терміни та визначення оригінал документа: ТИПИ СИСТЕМ І МЕРЕЖ 90. Абонентська система обробки даних Абонентська система Subscriber system Система обробки даних, … … Словник-довідник термінів нормативно-технічної документації

СТ СЭВ 4291-83: Машини обчислювальні та системи обробки даних. Пакети магнітних дисків ємністю 100 та 200 Мбайт. Технічні вимоги та методи випробувань- Термінологія СТ СЭВ 4291 83: Машини обчислювальні та системи обробки даних. Пакети магнітних дисків ємністю 100 та 200 Мбайт. Технічні вимоги та методи випробувань: 8. Амплітуда сигналу з інформаційної поверхні VТАА Усереднена по всій … Словник-довідник термінів нормативно-технічної документації

Геофізичні методи розвідки- дослідження будови земної кори фізичними методами з метою пошуків та розвідки корисних копалин; розвідувальна геофізика складова частина геофізики. Р. м. н. засновані на вивченні фізичних полів. Велика Радянська Енциклопедія

Книги

• Обчислювальні методи. Навчальний посібник, Амосов Андрій Авенірович, Дубінінський Юлій Андрійович, Копченова Наталія Василівна. У книзі розглядаються обчислювальні методи, що найчастіше використовуються в практиці прикладних та науково-технічних розрахунків: методи розв'язання задач лінійної алгебри, нелінійних рівнянь,…

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

методи апроксимації; 3) прямі (точні) методи; 4) ітераційні методи; 5) методи статистичних випробувань (методи Монте-Карло). p align="justify"> Метод, який здійснює обчислення рішення конкретної задачі, може мати досить складну структуру, але його елементарними кроками, є, як правило, реалізації зазначених методів. Дамо про них загальне уявлення.

1. Методи еквівалентних перетворень.

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

Приклад 3.13. Еквівалентне перетворення квадратного рівняння до виду (виділення повного квадрата) зводить завдання до проблеми обчислення квадратного кореня і призводить до відомих для її коренів формул (3.2).

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

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

2. Методи апроксимації.

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

Приклад 3.15. Один із найпростіших способів обчислення інтеграла полягає в апроксимації інтеграла на підставі формули прямокутників величиною

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

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

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

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

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

Наприклад, якщо для взяти то вийде уточнене значення

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

3. Прямі методи.

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

Приклад 3.18. Метод обчислення коріння квадратного рівняння за формулами є прямим методом. Елементарними тут вважаються чотири арифметичні операції та операція вилучення квадратного кореня.

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

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

Приклад 3.19 (схема Горнера). Нехай завдання полягає у обчисленні значення багаточлена

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

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

Розстановка дужок диктує такий порядок обчислень: Тут обчислення значення зажадало виконання лише операцій множення та операцій складання.

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

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

4. Ітераційні методи.

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

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

Зауважимо, що ітераційні методи широко використовуються при вирішенні найрізноманітніших завдань із застосуванням ЕОМ.

Приклад 3.20. Розглянемо відомий ітераційний метод, призначений для обчислення (де метод Ньютона. Задамо довільне початкове наближення). Продовжуючи цей процес далі, отримаємо і наближення обчислюється через за рекурентною формулою

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

Обчислимо з його допомогою значення на -розрядної десяткової ЕОМ. Задамо (як у прикладі 3.17). Тоді Подальші обчислення безглузді, оскільки через обмеженість розрядної сітки всі наступні уточнення будуть давати той самий результат. Однак порівняння з точним значенням показує, що вже на третій ітерації було отримано 6 вірних цифр.

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

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

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

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

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

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

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

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

Наприклад, для методу Ньютона (3.13) справедлива наступна апостеріорна оцінка:

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