Реферати українською » Математика » Обчислювальні методи алгебри (лекції)


Реферат Обчислювальні методи алгебри (лекції)

Страница 1 из 2 | Следующая страница

§1. Облік похибок обчислень.


За позитивного рішення математичних завдань виникатимуть похибки з різних причин:

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

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

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

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

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

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

Якщо , то а взято із нестачею.

Якщо , то а взято з головою.

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

Кажуть, що наближення а наближає число x з точністю до , якщо , , .

Приклад. Нехайа=0,273 – близьке значення x з точність до 0,001. Вказати кордону, у яких полягає x.

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

, – порядок округлення розряду.

Визначення. >Относительной похибкою наближеного значення а числа x називається ставлення

.

Приклад. >Округлить до десятих число 27,52 і знайти похибка і відносну похибка округлення:

,

,

.

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

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

>Установим зв'язок між межами похибок абсолютна і відносної:

- кордон відносної похибки;

- кордон абсолютної похибки.

.


§10. Допоміжні дані з функціонального аналізу.


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

  1. ;

  2. ;

– відстань між x і y.

1-3 – аксіоми метрики.


Кажуть, що багато елементів - метричне простірсходиться до , якщо

, .

Послідовність точок називається>сходящейся у собі (фундаментальної), якщо .

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


Визначення. >Метрическое простір, у якому всяка фундаментальна послідовність сходиться називаєтьсяповним.


Приклад. .

Поставимо у різний спосіб відстані:

  1. кубічна метрика,m-метрика

;

  1. сферична метрика, метрика

;

  1. >октаедрическая,s-метрика

.

Всім виконуються аксіоми метрики в кожній – повне метричне простір.


НехайX,Y – метричні простору.

називаєтьсяоператором, заданим в X багатозначно в Y.

ЯкщоX=Y, то – оператор, відображає Х у собі (перетворення).

Якщо , то – нерухома точка при відображенні .


Визначення. Кажуть, що відображення називається стискаючим (на стиснення), якщо .


§11. Рішення рівнянь з однією невідомим.Дихотомия.


Нехай потрібно вирішити рівняння (1), де – безперервна функція.

Кількість називаєтьсякоренем рівняння (1), якщо .

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

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

Для відділення коренів можна застосувати наступнийознака:

Коли відрізку функція безупинна і монотонна, і кінцях відрізка приймає значення різних знаків, то, на даному відрізку є тільки один корінь рівняння (1).

Достатнім умовою монотонності функції на відрізку є збереження знака похідною.

Відокремити корінь можна й графічно: намалювати графік і зазначити точки перетину з віссю Ой.

Доконаний метод відділення коренів – метод Штурму.

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

  1. Нехай

існує хоча б тільки корінь на ;

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

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

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

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

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


§12. Метод простий ітерації на вирішення алгебраїчних і трансцендентних рівнянь.


ТЕОРЕМА 1. (Принцип Банаха стискальних відбиття).

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

, де - довільний.

План докази.

  1. – фундаментальна

(*)

>q – коефіцієнт стискування

.

  1. >Т.к. R – повне метричне простір, у ньому всяка фундаментальна послідовність сходиться.

– сходиться, , причому , тобто. – нерухома точка.

  1. – єдина.

>ЧТД.


- послідовність наближення до вирішення рівняння


Метод – метод простий ітерації.

Якщо (*) зафіксувати, а , то

– оцінка похибки, оцінка швидкості збіжності.

зі швидкістю геометричній прогресії.

– лінійна швидкість збіжності.

Метод простий ітерації має лінійну швидкість збіжності.

Нехай (2), – речовинна функція.

Необхідно призвести до виду .

, -знакопостоянная безперервна функція.


Умова збіжності для цього методу:

ТЕОРЕМА 2.

Нехай виконуються умови:

  1. Функція – визначена і безупинна на відрізку на цьому відрізку задовольняє умовіЛипшица: ;

  2. Для початкового наближення виконується умова ;

  3. >Числа пов'язані умовою .

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

Теорему доводиться аналогічно теоремі Банаха з точністю до позначень.

Зауваження. УмоваЛипшица застосовувати важко, замість нього застосовують інше умова:

на відрізку

.

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

  1. по сусіднім наближенням

задається рівень зупинки і момент зупинки n задається формулою

  1. поневязке

задається рівень добробуту і момент зупинки nитерационной процедури задаєтьсянеравенствами

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

Недолік: невисока швидкість збіжності, тобто. лінійна.


§13. Метод Ньютона. Рішення рівнянь з одного перемінної.


Нехай потрібно вирішити рівняння (1), де функція – двічінепреривно-дифференцируема на ; на й .

З положень цих умов випливає, що у функція має сенс тільки один корінь.

Перш, ніж використовувати ітерації, необхідно (1) призвести до виду .

.

Функція безперервна на околиці кореня рівняння (1). Отже, рівняння (1) і рівняння (2) матимуть і той ж корінь .

Як виберемо , тоді (3)

>Виберем початкова наближення досить близький до . Інші наближення виходять за такою формулою:

(4)

Метод, певний (4), називаєтьсяметодом Ньютона.

>Докажем, що метод Ньютона сходиться й одержимо оцінку похибки.

Якщо дано, що , де – символ Ландау:

  • якщоk=1, то швидкість збіжності лінійна;

  • якщоk=2, то швидкість – квадратична;

  • якщоk=3, то швидкість – кубічна;

  • якщоk>1, то відповідність методусверхлинейная.


>Докажем, що (4) сходиться.

І тому покажемо, що відображення – стиснення, де .

.

При одержимо

.

По безперервності функції на є така околиця точки , що з , , а цьому стиснення.

Тому до відображенню можна застосувати принципсжатихотображений.

Якщо вибрати , він сходитися до точному рішенню рівняння (1)., тобто. .

Зауважимо, що метод (4) буде сходитися, якщо початкова наближення вибиратимемо з околиці

, .

>Докажем, що метод Ньютона сходиться.

>Определим швидкість збіжності методу Ньютона. І тому розкладемо до кількох Тейлора у точці .

.

При маємо . Тому

>Виразим (5)

Означимо через ,

(6)

, швидкість збіжності методу Ньютона квадратична, .

>Потребуем, щоб початкова умова вибиралося з умови

(7)

Тоді з (6) одержимо

- оцінка похибки.

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

>Достоинство: висока швидкість збіжності, легко програмується на ЕОМ.

Недоліки: вузька область збіжності.

Якщо будемо нічого вирішуватиоператорное рівняння , то, на кожен крок необхідно знаходити значення зворотного оператора .

>Геометрический сенс методу Ньютона.

П
>усть потрібно вирішити рівняння й єдине коріння цієї рівняння перебуває в .

У точці проведемо дотичну до графіка функції , рівняння дотичній: .

Якщо , то

– перше наближення до рівняння (1) методом Ньютона.

Візьмемо і проведемо дотичну у цій точці. Одержимо .

Якщо , то

– друге наближення до рівняння (1) методом Ньютона.

І далі. Звідси метод Ньютона називаютьметодом дотичних.


§14. Методхорд. Метод січних.


По колишньому вирішуємо рівняння (1), де , на і .

Тобто. на (1) має сенс тільки один корінь.

>Уравнение (1) запишемо як , де . Візьмемо як , де задовольняє умові , .

Тодіитерационний метод запишеться так:

методхорд.

>Докажем, що методхорд сходиться. І тому необхідно показати, що .

Розкладемо до кількох Тейлора

.

Розглянемо при .

.

Означимо через

Тобто. .

.

Отже, – стиснення і з принципу Банаха методхорд сходиться.

Одержимо оцінку похибки для методухорд

Оскільки , то

.

Означимо через - оцінка похибки для методухорд.

>Сходимость методихорд – лінійна.

>Достоинство методухорд – легкість програмування на ЕОМ.

загальний вигляд методухорд.

Загальний вид спроститься:

  • За умов , то , ;

  • За умов , то , .

Метод січних.

Метод січних має вигляд:

.

Швидкість збіжності –сверхлинейная.

.

Метод січних сходиться швидше методухорд і методу простий ітерації.


§15. Метод Гаусса рішення систем рівнянь.


Аби вирішити систем рівнянь використовують методи: точні і наближені.

До точним ставляться:

  • метод Гаусса;

  • метод Крамера;

  • метод оптимального винятку;

  • метод квадратного кореня.

До наближеним методам рішення систем рівнянь ставляться:

  • метод простий ітерації;

  • методЗейделя;

  • метод Ньютона.


Метод Гаусса у тому, щоб вихідну систему видуАх=b (1) із довільною матрицею А зводити до системі виду:

(2), де - вже трикутна матриця.

Процес відомості системи (1) до системи (2) називається прямим ходом методу Гаусса.

А перебування невідомих - зворотний хід методу Гаусса.

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

, де

Елементи контрольного шпальти перетворюються за тими самими формулам, як і елементи матриці А.

Другий крок контролю полягає у перевірці рівності суми елементів реформованій рядки - і контрольного елемента. Ці величини мають співпадати з точністю до 1,2 одиниць останнього розряду.

Метод Гаусса з головного елемента.

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

Потім рівняння ділять цей головні елементи і з інших рівнянь системи виключають невідомі, зумовлені цим головним елементом.

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

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

Через війну перетворень дійшли одиничної матриці.

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


§16. Метод квадратного кореня.


Метод квадратного кореня – точний метод рішення систем рівнянь і його на вирішення систем рівнянь, якщо матриця А – симетрична, тобто. .

,

де З – верхня трикутна матриця;

–транспонированная, ;

D – діагональна, .

>Подставим матрицю На систему (1)Ах=b.

(2)

Тоді

(3)

>Виразим елементи матриці З через елементи вихідної матриці А.

,

,

(*)

(4)

З (4) матимемо висловлювання через :

Нехай , тоді

Нехай , тоді

Нехай , тоді

З формули (*) отримуємо:

,

Отримали формули:


,


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

(Суворий облік похибки)


Нехай , де – число із наперед заданими своїмиприближениями з точністю до : .

Означимо через .

, де - кордон похибки суми наближеного значення .

Твердження 1. Сума кордонів похибок наближених доданків є кордоном похибки їх алгебраїчній суми.

Доказ: .

>ЧТД.

Твердження 2. Серед кордонів відносної похибки суми наближених доданків є така, яка перевершує найбільшої за межі відносної похибки доданків:

.

Твердження 3. Сума кордонів відносних похибоксомножителей є кордоном відносної похибки їх твори:

.

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

Слідство 2. Твір кордону відносної похибки наближеного значення а числа x на є кордоном відносної похибки результату спорудження числа а цілу позитивну ступінь n:

.

Слідство 3. Приватне кордону відносної похибки наближеного значення а числа x і n є кордоном відносної похибки кореня енну кількість ступеня з а:

.

Слідство 4. Сума кордонів відносних похибок наближених значень діленого і дільника є кордоном відносної похибки приватного.


§3. Наближені обчислення не враховуючи похибок.


Правило 1. А, щоб вирахувати алгебраїчну суму наближених доданків потрібно:

  1. серед доданків вибрати найменш точне (має найменше число розрядів після коми);

  2. й інші складові округлити, зберігаючи один запасний розряд, наступний за останнім розрядом виділеного доданка;

  3. скласти отримані після округлення числа;

  4. округлити отриманого результату до передостаннього розряду.

Приклад. >S=2.737+0.77974+27.1+0.2832.74+0.78+27.1+0.2830.9030.9.

Визначення 1. >Значащими цифрами в десяткової записи числа називається усі його цифри крім нулів, записаних зліва першої цифри не рівної 0.

0,00237 – 3 значущі цифри;

0,02000 – 4 значущі цифри.

Правило 2. А, щоб вирахувати твір (розподіл) наближених чисел потрібно:

  1. виділити множене, у якому найменше число значущих цифр;

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

  3. зробити множення (розподіл);

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

Приклад. >Р=3,34*0,7*4,748=4,7*3,3*0,710,6571*.

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

Правило 4. Якщо є наслідком проміжних дій, слід зберегти у ньому на 1-2 цифри більше, ніж зазначено в правилах 1-3.


§4. Зв'язок між числом кількості вірних цифр

і відносній похибкою.


Нехай

Страница 1 из 2 | Следующая страница

Схожі реферати:

  • Реферат на тему: Обчислювальний експеримент
    Державний Комітет Російської Федерації з вищої освіти >Якутский Державний Університет їм. М.К.
  • Реферат на тему: Гамма функції
    >Бета-функции                                                  6                            >Бета
  • Реферат на тему: Геометричні побудови
      План.    I.  Запровадження.  II. >Геометрические побудови. 1.Розподіл відрізків.
  • Реферат на тему: Bilet
    >Билет№1 1) Функція >y=F(x) називається періодичної, якщо є така кількість Т, нерівний нулю, що з
  • Реферат на тему: Hpor
    >Билет№1 1)Функція >y=F(x) називається періодичної, якщо є така кількість Т, нерівний нулю, що з

Навігація