Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
КМД
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Конспект лекцій
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
Історія чисельних методів.
Можна виділити три основні періоди.
Перший почався (3 ÷ 4) тисячі років назад. Він був пов’язаний з веденням конторських книг, обчисленням площ, об’ємів, розрахунком найпростіших механізмів. Чисельними засобами служили спочатку власні пальці, а потім – рахівниці. Вхідні дані містили мало цифр, більшість викладок виконувалось точно, без заокруглень.
Другий почався з Ньютона. В цей період вирішувались задачі астрономії, геодезії, розрахунку механічних конструкцій. Вони зводились або до алгебраїчних систем з великим числом невідомих, або до звичайних диференціальних рівнянь. Обчислення виконувались із заокругленням; часто від результату вимагалась висока точність, доводилось зберігати до 8 значущих цифр.
Обчислювальні засоби стали різноманітніші: таблиці елементарних функцій, потім арифмометр і логарифмічна лінійка, пізніше з’явились клавішні машини з електродвигуном. Але швидкість всіх цих засобів була невелика, обчислення займали дні, тижні і навіть місяці.
Третій період почався приблизно з 1940р. Військові задачі, наприклад, наводка зенітних гармат на швидкісний літак – вимагали від людини швидкості і призвели до розробки електричних систем. З’явились ЕОМ. Їх швидкодія настільки перевищувала швидкодію механічних засобів, що стало можливим проводити обчислення великого об’єму. Це дозволило чисельно вирішувати нові класи задач. Спочатку використовувались чисельні методи, які були розробленні в “доелектронному” періоді. Але застосування ЕОМ привело до переоцінки методів. Багато старих методів виявилось непридатними для автоматизованих обчислень. Почали скоро розроблятися нові методи, орієнтовані прямо на ЕОМ.
Чисельні методи – методи наближеного або точного рішення задач чистої або прикладної математики, що базуються на побудові скінченної послідовності дій над скінченою множиною чисел.
При рішенні задач прикладної математики найбільш ефективною вважають таку методологію. По-перше складають математичну модель. Її формулюють звичайно в термінах інтегральних і диференціальних рівнянь функцій неперервного аргументу. Це так звана континуальна математична модель. По-друге здійснюють перехід від континуальної математичної моделі до дискретної математичної моделі. Цей перехід полягає в заміні функції неперервного аргументу функціями дискретного аргументу, а рівняння континуальної математичної моделі – зазвичай різницевими рівняннями. При цьому інтеграл замінюють кінцевою сумою, а похідну – різницевим відношенням. Внаслідок цього приходять, як правило, до системи з великою кількістю рівнянь з багатьма невідомими (дискретна математична модель). По-третє складають обчислювальний алгоритм (ОА) для рішення одержаної системи рівнянь з деякою певною точністю. По-четверте здійснюють програмування.
Перехід від континуальної до дискретної математичної моделі приводить до появи похибки апроксимації. При практичних розрахунках необхідно враховувати і похибку заокруглення внаслідок обмеженої кількості значущих цифр при операціях в ЕОМ над машинними числами. Враховуючи це одержують реальний ОА. Це привело до необхідності проводити аналіз похибок і гарантовану оцінку точності реальних обчислень.
Особливe значення при цьому отримав аналіз стійкості ОА. Мається на увазі аналіз критеріїв і умов росту похибок заокруглення і апроксимації. В багатьох обчислювальних алгоритмах, розроблених до появи ЕОМ, враховувались тільки похибки апроксимації, а похибки заокруглення не бралися до уваги, внаслідок чого ці ОА часто виявлялись нестійкими.
Практичний інтерес представляють лише ті наближені алгоритми, які володіють властивістю збіжності. Алгоритм збіжний, якщо існують параметри, належний вибір яких (при умові точного завдання вхідних даних і точного виконання елементарних операцій) дозволяє зробити похибку δ як завгодно малою для вхідних функцій із заданого класу.
Система параметрів називається мінімальною для наближеного аргументу, якщо відмова від будь-якої з них порушує властивість збіжності.
Стійкість означає, що малі зміни вхідних даних приводять до малих змін результату.
Похибки по різному впливають на хід обчислення. Одні похибки зменшуються і при цьому не складають серйозних труднощів, а другі можуть зростати настільки сильно, що обчислення може виявитися непотрібним. Стійкість чисельного методу залежить від швидкості росту таких похибок. Чи будуть малі вихідні похибки породжувати невеликі похибки результатів? Якщо так, то метод стійкий; однак якщо навіть малі вихідні похибки надають згубну дію на результат, то метод виявляється нестійким.
Математичні моделі і чисельні методи
Відомо, що сучасних інженерів, дослідників в області електронної техніки, автоматики і т.д. математика цікавить перш за все як засіб розв’язування практичних задач, котрі виникають в даній області. Наприклад, потрібно побудувати систему автоматичного регулювання або якусь аналогову, цифрову схему. Одним із методів розв’язування є експеримент надто повільний і, як правило, дорогий метод. Приклад із своєї області – (BRM, RD). Як побачимо далі, експеримент використовують з метою перевірки математичної моделі.
Другий метод – математичний аналіз даної схеми або пристрою. Але такий метод застосовується не до реальних явищ, а до деяких математичних моделей цих явищ. Тому, перший етап роботи – це формування математичної моделі (постановка задачі).
Звичайно явища, що вивчаються, як правило, складні. Математична модель повинна охоплювати важливі сторони явища (для даної задачі). Якщо математична модель вибрана недостатньо ретельно, то, незалежно від застосовуваних методів розрахунку, всі результати будуть недостатньо надійними, а в деяких випадках можуть бути і неправильними.
Другий етап роботи – математичні дослідження. В залежності від складності моделі застосовуються різні математичні підходи. Для найбільш грубих і нескладних моделей часто вдається отримати аналітичний розв’язок. Для більш точних і складних моделей аналітичний розв’язок вдається отримати порівняно рідко. Наcамкінець, для найбільш важких і точних моделей основним методом роз’язку є чисельні, як правило, вони потребують розрахунку на ЕОМ.
Третій етап роботи – це осмислення математичного розв’язку і співставлення його з експериментальними даними. Якщо розрахунок і експеримент не узгоджуються, то модель необхідно переглянути і уточнити.
Чисельні методи є одними із потужних засобів розв’язування задач. Є задачі, де без достатньо складних чисельних методів не вдалося одержати відповіді; класичний приклад – відкриття Нептуна по аномаліях руху Урана. Часто потрібно велике число дій за короткий час, інакше відповідь буде непотрібна. Наприклад, добовий прогноз погоди повинен бути вирахуваний за декілька годин; корекцію траєкторії польоту ракети потрібно розрахувати за декілька хвилин (а іноді і секунд); режим роботи прокатного стана повинен коригуватися за секунду. Це є неможливим без застосування потужних ЕОМ.
Сучасні чисельні методи і потужні ЕОМ дали можливості вирішувати багато складних задач. Але застосовувати чисельні методи непросто. ЕОМ – це засіб праці сучасного інженера, яка може виконувати тільки елементарні арифметичні і логічні операції. Тому під час розробки автоматичної моделі, потрібна ще розробка алгоритму, який зводить всі обчислення до послідовності алгоритмічних і логічних дій. Сам алгоритм і програма повинні бути ретельно пеоревірені, про це свідчить навіть відомий вислів: “в будь-якій найменшій програмі є хоч одна помилка ”. Перевірка алгоритму є ще складнішою, бо для складних алгоритмів не часто вдається доказати збіжність класичними методами.
Розділ математики, який має справу із створенням і впровадженням чисельних алгоритмів для розв’язування складних задач різноманітних сфер науки, часто називають прикладною математикою.
Головна задача прикладної математики – фактичне знаходження розв’язку з необхідною точністю; цим вона відрізняється від класичної математики, яка основну увагу приділяє дослідженню умов існування і властивостей розв’язку.
Теоретично дослідження в сфері чисельних методів в основному групуються навколо типових математичних задач: задачі аналізу (наближення функцій, наближені диференціювання і інтегрування), задачі алгебри, розв’язування диференціальних і інтегральних рівнянь, задачі оптимізації і т.д.
Похибки обчислень.
Джерела і класифікація похибок.
Похибки обчислень зумовлені наступними причинами:
Математичний опис задачі являється неточним, зокрема неточно задані початкові дані опису.
Вживаний для розв’язку метод часто не є точним; одержання точного розв’язку вимагає необмеженого або недопустимо великого числа арифметичних операцій, тому замість одержання точного розв’язку задачі користуються наближеним розв’язком.
При вводі даних в машину, при виконанні арифметичних операцій і при виводі даних виконуються округлення.
Похибки, що відповідають цим причинам, називають:
неусувна похибка;
похибка методу;
обчислювальна похибка.
Основні задачі дослідження похибок.
Оцінка точності результату в залежності від різних видів похибок або оцінка повної похибки;
Створення алгоритмів, які забезпечують максимальну точність при виконанні мінімального об’єму обчислень.
Нехай А – точне значення деякої величини, а – відоме наближення до нього (наближене значення). Тоді
Δ = │А – а│
називають абсолютною похибкою числа а, а
– відносною похибкою числа.
Слід розрізняти два випадки:
число А нам відоме, тоді Δ обчислюється за формулою;
число А – невідоме, що буває найчастіше, і отже, не можна визначити абсолютну похибку за формулою. В цьому випадку замість невідомої теоретичної абсолютної похибки Δ вводять її оцінку зверху, так звану граничну абсолютну похибку Δа. Тоді
Δ = │А – а│≤ Δа.
Звідси випливає, що точне значення А міститься в межах
а – Δа ≤ А ≤ а + Δа ,
або А = а ± Δа
Граничною відносною похибкою δа називається будь-яке число таке, що
δа ≥ δ ;
Оскільки А звичайно невідоме, то зручно δа виразити через а. Як правило Δа << a, тому наближено
та Δа ≈│а│ δа .
Заокруглення чисел.
Досить часто виникає необхідність в заокругленні числа а, тобто зміні його числом а1 з меншою кількістю значущих цифр. Число а1 вибирають так, щоб похибка заокруглення була мінімальна.
Правила округлення за доповненням.
Щоб заокруглити число n до значущих цифр, відкидають всі його цифри, що стоять справа від n-ї значущої цифри, або якщо це потрібно для збереження розрядів, замінюють їх нулями.
При цьому:
якщо перша з відкинутих цифр менша 5-ти, то залишені десяткові знаки зберігаються без змін;
якщо перша з відкинутих цифр бульша 5-ти, то до останньої залишеної цифри додається одиниця;
якщо перша з відкинутих цифр дорівнює 5-ти, та серед решти відкинутих цифр є ненульові, то остання залишена цифра збільшується на одиницю;
якщо перша з відкинутих цифр дорівнює 5-ти, та серед решти відкинутих цифр є нульові, то остання залишена цифра зберігається незмінною, якщо вона парна і збільшується на одиницю, якщо вона непарна (правило парної цифри).
Значущі цифри. Число вірних знаків.
Значущими цифрами наближеного числа а називають всі цифри в його десятковому наближенні, відмінні від нуля, та нулі, якщо вони стоять між іншими значущими цифрами або розміщенні в кінці числа і вказують на точність. Однак точність наближеного числа залежить не від того, скільки в цьому числі значущих цифр, а від того, скільки значущих цифр заслуговує довір’я (тобто, скільки вірних значущих цифр).
Всяке додатне число а може бути представлене у вигляді розкладу
де К1, К2, … , Кn – десяткові знаки числа а. При цьому обов’язково К1 ≠ 0, К2, … , Кn можуть приймати значення від 0 до 9.
Певне число а має n точних десяткових знаків, якщо його абсолютна похибка не перевищує одиниці n-го десяткового знаку або половину цієї одиниці у випадку заокруглення за доповненням, тобто
у широкому розумінні,
у вузькому розумінні
Зв’язок абсолютної похибки з числом вірних значущих цифр.
Між кількістю вірних десяткових знаків і відносною похибкою числа а існує зв’язок, який можна виразити за допомогою теорем:
Теорема 1.
Якщо додатнє число а має n десяткових знаків, то відносна похибка δ цього числа не перевищує , яка ділиться на першу значущу цифру даного числа, тобто
Тоді за визначенням
Δ = │А – а│≤ 10m–n+1
Теорема 2.
Якщо , то а має n вірних десяткових знаків
звідси ;
Наслідок: за граничну відносну похибку числа а можна прийняти
.
Похибка обчислення функції.
Нехай відомі похибки деякої системи величин. Потрібно визначити похибку даної функції від цих величин.
Нехай задана диференційованана функція
u = f (x1, x2, … , xn)
і нехай │Δxі│ (і = 1, 2, … , n) абсолютна похибка аргументів функції. Тоді абсолютна похибка функції
Як правило, на практиці │Δxі│ настільки мала величина, що добутками, квадратами і вищими степенями можна знехтувати. Тому можна покласти
Тут повний приріст замінюємо повним диференціалом, отже
(1)
Позначивши через Δxі (і = 1, 2, … , n) граничні абсолютні похибки аргументів xі, а через Δu – граничну похибку функції і для малих Δxі одержимо
– гранична абсолютна похибка функції (2)
Поділивши обидві частини нерівності (1) на │u│, одержимо оцінку для відносної похибки функції u
Тоді гранична відносна похибка
Наприклад, для двох змінних
Приклад. Знайти граничну абсолютну та відносну похибки об’єму шару , якщо r = 1,8 см ±0,005 см;
π ≈ 3,14.
Тут Δ r = 0,005
Δ π = 0,002, оскільки число π знаходиться в межах 3,14 < π < 3,142
Обчислимо
см3
Розглядаючи π та r як аргументи, знайдемо
Гранична абсолютна похибка:
Відносна похибка:
Таким чином V = 24,4 см3 ±0,22 см3;
Похибка суми.
Теорема 1.
Абсолютна похибка алгебраїчної суми декількох наближених чисел не перевищує суми абсолютних похибок цих чисел.
(1)
Гранична абсолютна похибка суми дорівнює сумі граничних абсолютних похибок доданків
(2)
Із формули (2) випливає, що гранична абсолютна похибка суми не може бути меншою граничної абсолютної похибки найбільш точного із доданків, тобто доданка, який має максимальну похибку. З якою б точністю не було визначено решта доданків, ми не можемо за їх рахунок збільшити точність суми. Тому не слід зберігати надлишкові знаки і в більш точних доданків.
Практичне правило для додавання наближених чисел. Щоб додати числа різної абсолютної точності необхідно:
Виділити числа, десятковий запис яких обривається раніше інших, (тобто числа, що мають найменшу абсолютну точність), і залишити їх без змін;
Числа, які залишилися, необхідно заокруглити по взірцю виділених, зберігаючи один або два запасних десяткових знаки;
Додати дані числа, враховуючи всі збережені знаки;
Одержаний результат заокруглити на один знак.
Теорема 2.
Якщо доданки мають однаковий знак, то гранична відносна похибка їх суми не перевищує найбільшої із граничних відносних похибок доданків.
Нехай , причому приймаємо, що хі > 0 (i = 1, 2, …, n).
Гранична відносна похибка
;
Нехай найбільша із граничних відносних похибок доданків , тобто <. Тоді
Отже , тобто .
Похибка різниці.
Розглянемо різницю двох наближених чисел
За формулою для граничної абсолютної похибки алгебраїчної суми одержимо
тобто абсолютна похибка різниці оцінюється так само, як і для суми.
Гранична абсолютна похибка різниці дорівнює сумі граничних абсолютних похибок зменшуваного і від’ємника.
Звідси гранична відносна похибка різниці:
(1)
Якщо наближені числа х1 і х2 достатньо близькі один до одного, то різниця мала. З формули (1) випливає, що гранична відносна похибка в цьому випадку може бути досить великою, в той час коли відносна похибка зменшуваного і від’ємника залишається малою, тобто тут відбувається втрата точності. Звідси випливає практичне правило: при наближених обчисленнях слід по можливості уникати віднімання двох рівних близьких чисел; якщо в силу необхідності доводиться віднімати такі числа, то слід зменшуване і від’ємник брати з достатнім числом запасних знаків (якщо існує така можливість). Наприклад, якщо відомо, що при відніманні чисел х1 і х2 перші m значущих цифр зникнуть, то слід брати х1 і х2 з (m + n) вірними значущими цифрами.
Приклад. Знайти різницю з трьома правильними знаками.
Оскільки ,
то результат u = 0,00353 = 3,53∙10– 3.
Цей результат можна отримати, якщо записати u у такому вигляді (перетворимо вираз, щоб уникнути віднімання двох близьких чисел)
і взяти корені лише з трьома правильними знаками
.
Похибка добутку.
Теорема.
Відносна похибка добутку декількох наближених чисел, відмінних від нуля, не перевищує суми відносних похибок цих чисел. Нехай
покладемо , одержимо δ ≤ δ1 + δ2 +…+ δn .
Формула правильна, якщо співмножники мають однакові або різницеві знаки.
Наприклад, u = x1 · x2
ln u = ln x1 + ln x2 ,
Наслідок. Гранична відносна похибка добутку дорівнює сумі граничних відносних похибок співмножників, тобто
Розглянемо частковий випадок
u = k · x , де k – точний множник, відмінний від нуля.
тобто при множенні наближеного числа на точний множник k відносна гранична похибка не змінюється, а абсолютна гранична похибка збільшується в │ k │ разів.
Правило: щоб знайти добуток декількох наближених чисел з різним числом правильних значущих цифр достатньо:
заокруглити їх так, щоб кожне з них мало на одну (або дві) значущих цифри більшу, ніж число правильних цифр в найбільш точному із співмножників;
в результаті множення зберегти стільки значущих цифр, скільки правильних цифр є в найбільш точному із співмножників (або утримати ще одну запасну цифру).
Похибка частки
Теорема:
Відносна похибка частки не перевищує суми відносних похибок діленого і дільника.
Нехай Тоді на основі одержимо
.
Наслідок. Якщо то
Нехай ділене х1 і дільник х2 мають щонайменше m вірних цифр. Якщо α і β їх перші значущі цифри, то за граничну відносну похибку частки u може бути прийнята величина
Звідси одержимо правило:
якщо α ≥ 2 і β ≥ 2, то частка u має щонайменше (m – 1) вірних знаків;
якщо α = 1 і β = 1, то частка u має (m – 2) вірних знаків.
Відносна похибка степеня.
Нехай (де m – натуральне число). Тоді
, де δ′ – відносна похибка числа
і ,
тобто гранична відносна похибка т-го степеня числа в т разів більша граничної відносної похибки самого числа.
Обчислення машинного епсилон.
Точність плаваючої арифметики можна характеризувати за допомогою машинного епсилон, тобто найменшого числа з плаваючою комою, такого що
1 ε > 1,
де означає плаваюче додавання.
Хоч це означення виділяє як машинне ε єдине число плаваючої системи, не так вже й важливо використовувати його точне значення. Воно використовується звичайно в програмах таким чином, що може відрізнятися від свого точного значення декількома степенями 2, не викликаючи при цьому серйозних труднощів.
Існує декілька методів для наближеного обчислення значення ε, таким чином програма може визначити точність машини, на якій вона виконується, під час свого виконання. Метод, яким можна обчислити наближення, котре відрізняється від ε щонайбільше множником 2, ілюструється наступним сегментом фортранної програми:
EPS = 1.
10 EPS = 0.5*EPS
EPS P1 = EPS + 1.
IF (EPS P1.GT.1) GO TO 10
Поняття про матриці.
Система чисел розташованих в прямокутній таблиці із “ т ” рядків та “ n ” стовпців називається матрицею розміру т n.
(1)
Числа аij , де i – номер рядка; j – номер стовпця – називають елементами матриці. Для матриці часто використовують скорочену форму запису
( ; )
або
Якщо матриця складається з одного рядка (тобто має порядок 1 n), то вона називається вектором-рядком
Якщо ж матриця складається з одного стовпця (т 1 – порядку) – вона називається вектором-стовпцем.
Якщо число рядків і стовпців однакове, то матриця називається квадратною (тобто т = n). Якщо т ≠ n, то – прямокутною. Число (скаляр) можна розглядати як матрицю 11.
Головною діагоналлю квадратної матриці називають діагональ, що проходить через верхній лівий і нижній правий кути, тобто сукупність елементів вигляду аіі, де .
Квадратна матриця вигляду
(2)
називається діагональною матрицею. Якщо при цьому αі = 1 , то матриця (2) називається одиничною і позначається буквою Е, тобто
Матриця, всі елементи якої рівні нулю, називають нульовою і позначається через нуль. При необхідності вказати число рядків і стовпців використовують позначення 0mn .
Дві матриці вважається рівними, якщо вони одного і того ж типу (розміру), тобто мають однакове число рядків і стовпців, і відповідні елементи їх рівні
А = В аij = bij
Додавання та віднімання матриць однакового розміру.
Добуток матриці А на число α (або навпаки) – це матриця, елементи якої одержуються множенням всіх елементів матриці А на число α
Добуток матриць.
Нехай А та В матриці порядків т n та n р відповідно. Добуток матриць
це матриця С розміру т р.
(; )
Правило множення: щоб одержати елемент , що стоїть в і – му рядку та j – му стовпці добутку двох матриць, необхідно елементи і – го рядка першої матриці помножити на відповідні елементи j – го стовпця другої матриці і одержані добутки додати.
Слід наголосити, що множення А на В допустиме (тобто добуток А ∙ В існує), якщо число стовпців А дорівнює числу рядків В.
Приклад.
.
Якщо в матриці т n
замінити рядки власними стовпчиками, то одержимо матрицю
розміру n т, котра називається транспонованою по відношенню до матриці А. Для вектора-рядка транспонованою матрицею є вектор-стовпчик.
Метод послідовних наближень (метод Пікара).
Нехай задано рівняння
або (1)
права частина якого в прямокутнику неперервна та має неперервну частинну похідну по у. Потрібно знайти розв’язок рівняння (1), що задовольняє початковій умові
х = х0 , у(х0) = у0 (2)
Інтегруючи обидві частини рівняння від х0 до х, одержимо:
або (3)
Рівняння (1) заміняється інтегральним рівнянням (3). Інтегральне рівняння (3) задовольняє диференціальне рівняння (1) і початковій умові (2). Дійсно
Замінюючи в рівності (3) функцію у значенням у0, одержимо перше наближення
(4)
Одержуємо послідовність функцій { уі (х) }, що збігається до функції у (х), яка є розв’язком диференціального рівняння у′ = f ( х, у )
у1 (х), у2 (х), у3 (х), …, уn (х)
Приклад.
Розв’язати методом Пікара диференціальне рівняння у′ = х2 + у2 . Початкові умови х0 = 0, у(х0)= = у0 = 0.
Переходимо до інтегрального рівняння
,
або з врахуванням початкових умов
Одержимо послідовні наближення
Метод Пікара зручно застосовувати, якщо інтеграли в (4) вдається обчислювати через елементарні функції. Якщо ж права частина рівняння (1) більш складна, то ці інтеграли доводиться знаходити чисельними методами, і методом Пікара не досить зручний.
29.05.2013 13:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора