Детерминанти
Понятието детерминанта
Всяка квадратна матрица от n-ти ред може да бъде свързана с извикано число детерминант (детерминант)
матрица A и се означава по следния начин: 
, или , или детайл А.
Детерминанта на матрица от първи ред, или детерминанта от първи ред, е елементът
Детерминанта от втори ред(детерминантата на матрица от втори ред) се изчислява, както следва:
 |
Ориз. Схема за изчисляване на детерминанта от втори ред
Така детерминантата от втори ред е сумата 2=2! членове, всеки от които е произведение на 2 фактора - елементи на матрица А, по един от всеки ред и всяка колона. Един от термините е взет със знак „+“, другият със знак „-“.
Намерете определителя
Детерминантата от трети ред (детерминанта от трети ред на квадратна матрица) се дава от:
Така детерминантата от трети ред е сумата 6=3! членове, всеки от които е произведение на 3 фактора – елементи на матрица А, по един от всеки ред и всяка колона. Едната половина от термините са взети със знака „+“, другата половина със знака „-“.
Основният метод за изчисляване на детерминанта от трети ред е т.нар правило на триъгълника (Правило на Сарус): първият от трите члена, включени в сумата със знака "+", е произведението на елементите на главния диагонал, вторият и третият са продуктите на елементите, разположени във върховете на два триъгълника с основи, успоредни на главния диагонал; трите члена, включени в сумата със знака "-", се определят по подобен начин, но спрямо втория (страничен) диагонал. По-долу има 2 схеми за изчисляване на детерминанти от трети ред
б)
Ориз. Схеми за изчисляване на детерминанти от 3-ти ред
Намерете детерминантата:
Детерминантата на квадратна матрица от n-ти ред (n 4) се изчислява, като се използват свойствата на детерминантите.
Основни свойства на детерминантите. Методи за изчисляване на детерминанти
Матричните детерминанти имат следните основни свойства:
1. Детерминантата не се променя, когато матрицата се транспонира.
2. Ако два реда (или колони) се разменят в детерминантата, детерминантата ще промени знака.
3. Детерминанта с два пропорционални (в частност равни) реда (колони) е равна на нула.
4. Ако ред (колона) в детерминанта се състои от нули, то детерминантата е равна на нула.
5. Общият множител на елементите на всеки ред (или колона) може да бъде изваден от детерминантния знак.
6. Детерминантата няма да се промени, ако към всички елементи на един ред (или колона) добавим съответните елементи от друг ред (или колона), умножени по същото число.
7. Детерминантата на диагоналните и триъгълните (горна и долна) матрици е равна на произведението на диагоналните елементи.
8. Детерминантата на произведението на квадратни матрици е равна на произведението на техните детерминанти.
Насоки за студенти от 1 курс
Базей Александър Анатолиевич
Одеса 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 km/h?
Получаваме решението веднага:
.
Малко вероятно е обаче някой да използва това математически точно решение и ето защо. Изчисленията са направени абсолютно точно, но точно ли е измерено разстоянието до станцията? Възможно ли е дори да се измери пътят на пешеходец, без да се правят грешки? Може ли пешеходецът да върви по строго определена линия в град, пълен с хора и автомобили, движещи се във всевъзможни посоки? А скоростта от 6 км/ч - определено ли е абсолютно точно? И така нататък.
Съвсем ясно е, че в този случай всеки ще предпочете не „математически точното“, а „практическото“ решение на този проблем, тоест ще прецени, че разходката ще отнеме 12-15 минути и ще добави още няколко минути, за да сте сигурни.
Защо тогава да изчисляваме секундите и техните части и да се стремим към такава степен на точност, която не може да се използва на практика?
Математиката е точна наука, но самото понятие „прецизност“ изисква изясняване. За да направим това, трябва да започнем с концепцията за число, тъй като точността на резултатите от изчислението до голяма степен зависи от точността на числата и надеждността на първоначалните данни.
Има три източника за получаване на числа: броене, измерване и извършване на различни математически операции
Ако броят на елементите, които трябва да се преброят, е малък и ако е постоянен във времето, тогава ще получим абсолютно точнорезултати. Например, на една ръка има 5 пръста, а в кутия има 300 лагера. Друго е положението, когато казват: в Одеса през 1979 г. имаше 1 000 000 жители. В крайна сметка хората се раждат и умират, идват и си отиват; техният брой се променя през цялото време, дори през периода от време, през който е завършено преброяването. Това, което наистина имаме предвид е, че е имало около 1 000 000 жители, може би 999 125, или 1 001 263, или някакво друго число близо до 1 000 000. В този случай 1 000 000 дава приблизителенброй жители на града.
Всяко измерване не може да бъде извършено абсолютно точно. Всяко устройство дава някакъв вид грешка. В допълнение, двама наблюдатели, измерващи едно и също количество с един и същи инструмент, обикновено получават леко различни резултати; пълното съвпадение на резултатите е рядко изключение.
Дори такова просто измервателно устройство като линийка има „грешка на устройството“ - краищата и равнините на линийката са малко по-различни от идеалните прави линии и равнини, щрихите върху линийката не могат да се прилагат на абсолютно равни разстояния, а самите щрихи имат определена дебелина; така че при измерване не можем да получим резултати, по-точни от дебелината на щрихите.
Ако сте измерили дължината на масата и сте получили стойност от 1360,5 мм, това изобщо не означава, че дължината на масата е точно 1360,5 мм - ако тази маса измерва друга или повторите измерването, тогава можете да получите стойност както на 1360,4 mm, така и на 1360,6 mm. Числото 1360,5 mm изразява дължината на масата приблизително.
Не всички математически операции могат да бъдат извършени без грешки. Не винаги е възможно да се извлече корен, да се намери синус или логаритъм, дори да се раздели с абсолютна точност.
Всички измервания без изключение водят до приблизителни стойности на измерваните величини. В някои случаи измерванията се извършват грубо, тогава се получават големи грешки; при внимателни измервания грешките са по-малки. Никога не се постига абсолютна точност на измерванията.
Нека сега разгледаме втората страна на въпроса. Необходима ли е абсолютна точност на практика и каква стойност е приблизителен резултат?
При изчисляване на електропровод или газопровод никой няма да определи разстоянието между опорите с точност до милиметър или диаметъра на тръбата с точност до микрон. В технологията и строителството всяка част или конструкция може да бъде произведена само с определена точност, която се определя от така наречените допуски. Тези допустими отклонения варират от части от микрон до милиметри и сантиметри, в зависимост от материала, размера и предназначението на частта или структурата. Следователно, за да се определят размерите на дадена част, няма смисъл да се извършват изчисления с точност, по-голяма от необходимата.
1) Първоначалните данни за изчисления, като правило, имат грешки, т.е. те са приблизителни;
2) Тези грешки, често увеличени, влизат в резултатите от изчислението. Но практиката не изисква точни данни, а се задоволява с резултати с някои допустими грешки, чиято величина трябва да бъде предварително определена.
3) Възможно е да се осигури необходимата точност на резултата само когато изходните данни са достатъчно точни и когато се вземат предвид всички грешки, въведени от самите изчисления.
4) Изчисленията с приблизителни числа трябва да се извършват приблизително, като се опитват да постигнат минимален разход на труд и време при решаване на проблема.
Обикновено в техническите изчисления допустимите грешки варират от 0,1 до 5%, но в научните въпроси те могат да бъдат намалени до хилядни от процента. Например, при изстрелването на първия изкуствен спътник на Луната (31 март 1966 г.) трябваше да се осигури скорост на изстрелване от около 11 200 м/сек с точност от няколко сантиметра в секунда, за да може спътникът да навлезе в окололунна по-скоро отколкото околослънчева орбита.
Освен това имайте предвид, че правилата на аритметиката се извеждат при предположението, че всички числа са точни. Следователно, ако изчисленията с приблизителни числа се извършват като с точни, тогава се създава опасно и вредно впечатление за точност там, където в действителност няма такава. Истинската научна и по-специално математическа точност се състои именно в това да се посочи наличието на почти винаги неизбежни грешки и да се определят техните граници.
Въз основа на концепциите за детерминанти от втори и трети ред, можем по подобен начин да въведем концепцията за детерминанта на реда н. Детерминанти от порядък по-висок от трети се изчисляват, като правило, като се използват свойствата на детерминантите, формулирани в параграф 1.3., които са валидни за детерминанти от всякакъв ред.
Използвайки свойството на детерминанти номер 9 0, въвеждаме дефиницията на детерминанта от 4-ти ред:
Пример 2.Изчислете с подходящо разширение.
По подобен начин се въвежда понятието детерминанта на 5-ти, 6-ти и т.н. поръчка. Така детерминантата от ред n:
.
Всички свойства на детерминанти от 2-ри и 3-ти ред, разгледани по-рано, са валидни и за детерминанти от n-ти ред.
Нека разгледаме основните методи за изчисляване на детерминанти н-та поръчка.
коментар:Преди да приложите този метод, е полезно, като използвате основните свойства на детерминантите, да обърнете към нула всички елементи на определен ред или колона с изключение на един. (Ефективен метод за намаляване на поръчките)
Метод на редукция до триъгълна форма се състои в такова преобразуване на определителя, когато всички негови елементи, лежащи от едната страна на главния диагонал, станат равни на нула. В този случай детерминантата е равна на произведението на елементите на неговия главен диагонал.
Пример 3.Изчислете чрез привеждане до триъгълна форма.
Пример 4.Изчислете, като използвате метода за ефективно намаляване на поръчката
.
Решение: съгласно свойството на 4 0 детерминанти, ще извадим фактора 10 от първия ред и след това ще умножим последователно втория ред по 2, по 2, по 1 и ще го съберем с първия, третия и четвъртия редове, съответно (свойство 8 0).
.
Получената детерминанта може да бъде разширена в елементи от първата колона. Тя ще бъде намалена до детерминанта от трети ред, която се изчислява с помощта на правилото на Sarrus (триъгълник).
Пример 5.Изчислете детерминантата, като я редуцирате до триъгълна форма.
.
Пример 3.Изчислете с помощта на рекурентни отношения.
.
.
Лекция 4. Обратна матрица. Ранг на матрицата.
1. Концепцията за обратна матрица
Определение 1. Квадрат се нарича матрица A от ред n неизроден,ако неговата детерминанта | А| ≠ 0. В случай, когато | А| = 0, се извиква матрица A изродени.
Само за квадратни неособени матрици A е въведено понятието обратна матрица A -1.
Определение 2 . Извиква се матрица A -1 обратенза квадратна неособена матрица A, ако A -1 A = AA -1 = E, където E е единичната матрица от ред н.
Определение 3
.
Матрица 
Наречен анексираннеговите елементи са алгебрични допълнения 
транспонирана матрица 
.
Алгоритъм за изчисляване на обратната матрица с помощта на метода на свързаната матрица.
, Където 
.
Проверяваме правилността на изчислението A -1 A = AA -1 = E. (E е матрицата на идентичност)
Матрици А и А -1 реципрочен. Ако | А| = 0, тогава обратната матрица не съществува.
Пример 1.Дадена е матрица A. Уверете се, че тя е неособена и намерете обратната матрица 
.
Решение: 
. Следователно матрицата е неединична.
Нека намерим обратната матрица. Нека съставим алгебрични допълнения на елементите на матрица А.
Получаваме 
.
Представяне както на изходните данни в задачата, така и на нейното решение - като число или набор от числа
Той е важен компонент в системата за обучение на инженери по технически специалности.
Основата на изчислителните методи са:
- решаване на системи от линейни уравнения
- интерполация и изчисляване на приблизителна функция
- числено решение на обикновени диференциални уравнения
- числено решение на частични диференциални уравнения (уравнения на математическата физика)
- решаване на оптимизационни проблеми
Вижте също
Бележки
Литература
- Калиткин Н. Н. Числени методи. М., Наука, 1978
- Амосов А. А., Дубински Ю. А., Копченова Н. В. “Изчислителни методи за инженери”, 1994 г.
- Fletcher K, Изчислителни методи в динамиката на флуидите, изд. Свят, 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
Връзки
- Научно списание “Изчислителни методи и програмиране. Нови компютърни технологии"
Фондация Уикимедия. 2010 г.
- Изчислителна математика и математическа физика
- Изчислителен конвейер
Вижте какво представляват „изчислителни методи“ в други речници:
Методи на електроаналитичната химия- Съдържание 1 Методи на електроаналитичната химия 2 Въведение 3 Теоретична част ... Wikipedia
Методи за кодиране на цифров сигнал- В тази статия липсват връзки към източници на информация. Информацията трябва да може да се провери, в противен случай може да бъде поставена под съмнение и изтрита. Можете да... Уикипедия
ЧИСЛЕНИ МЕТОДИ В ГАЗОДИНАМИКАТА- методи за решаване на проблеми от газовата динамика, базирани на изчислителни алгоритми. Нека разгледаме основните аспекти на теорията на числените методи за решаване на проблеми с газовата динамика, записвайки уравненията на газовата динамика под формата на закони за запазване в инерционния... ... Математическа енциклопедия
ДИФУЗИОННИ МЕТОДИ- методи за решаване на кинетика. уравнения за пренос на неутрони (или други частици), които модифицират уравненията за приближение на дифузията. Тъй като дифузионното приближение дава правилната форма на асимптотичното уравнение. решаване на транспортното уравнение (далеч от източници и... ... Математическа енциклопедия
МЕТОДИ ЗА МИНИМИЗАЦИЯ НА ФУНКЦИИ НА ГУЛИШ- числени методи за намиране на минимуми на функции на много променливи. Нека е дадена функция, ограничена отдолу, два пъти непрекъснато диференцируема по отношение на нейните аргументи, за която е известно, че за определен вектор (транспониран знак) е необходимо... ... Математическа енциклопедия
GOST R 53622-2009: Информационни технологии. Информационни и изчислителни системи. Етапи и етапи на жизнения цикъл, видове и пълнота на документите- Терминология GOST R 53622 2009: Информационни технологии. Информационни и изчислителни системи. Етапи и етапи от жизнения цикъл, видове и пълнота на документите оригинален документ: 3.1 хардуерна софтуерна платформа: Унифициран набор от инструменти... ...
Приложни изчислителни системи- Приложните изчислителни системи, или ABC, включват системи за обектно смятане, базирани на комбинаторна логика и ламбда смятане. Единственото нещо, което е значително развито в тези системи, е идеята за обекта. В... ... Уикипедия
GOST 24402-88 Телеобработка и компютърни мрежи. Термини и дефиниции- Терминология GOST 24402 88: Телеобработка и компютърни мрежи. Термини и определения оригинален документ: ВИДОВЕ СИСТЕМИ И МРЕЖИ 90. Система за обработка на абонатни данни Абонатна система Абонатна система Система за обработка на данни,… … Речник-справочник на термините на нормативната и техническата документация
ST SEV 4291-83: Компютърни машини и системи за обработка на данни. Пакети от магнитни дискове с капацитет 100 и 200 MB. Технически изисквания и методи за изпитване- Терминология ST SEV 4291 83: Компютърни машини и системи за обработка на данни. Пакети от магнитни дискове с капацитет 100 и 200 MB. Технически изисквания и методи за изпитване: 8. Амплитуда на сигнала от информационната повърхност на VTAA Осреднена за цялата ... Речник-справочник на термините на нормативната и техническата документация
Геофизични методи за проучване- изследване на структурата на земната кора с помощта на физични методи с цел търсене и проучване на полезни изкопаеми; проучвателната геофизика е неразделна част от геофизиката (виж Геофизика). Г.м.р. въз основа на изследването на физическите полета... ... Велика съветска енциклопедия
Книги
- Изчислителни методи. Учебник, Андрей Авенирович Амосов, Юлий Андреевич Дубинински, Наталия Василиевна Копченова. В книгата се разглеждат изчислителните методи, най-често използвани в практиката на приложните и научно-техническите изчисления: методи за решаване на задачи от линейната алгебра, нелинейни уравнения,...
След като обсъдихме някои важни характеристики на изчислителните проблеми, нека насочим вниманието си към тези методи, които се използват в изчислителната математика за трансформиране на проблеми във форма, удобна за изпълнение на компютър и позволяват изграждането на изчислителни алгоритми. Ще наричаме тези методи изчислителни. С известна степен на условност изчислителните методи могат да бъдат разделени на следните класове: 1) методи на еквивалентни трансформации; 2)
апроксимационни методи; 3) директни (точни) методи; 4) итеративни методи; 5) статистически методи за тестване (методи на Монте Карло). Метод, който изчислява решение на конкретен проблем, може да има доста сложна структура, но неговите елементарни стъпки, като правило, са изпълнението на посочените методи. Нека да дадем обща представа за тях.
1. Методи на еквивалентни трансформации.
Тези методи ви позволяват да замените оригиналния проблем с друг, който има същото решение. Извършването на еквивалентни трансформации се оказва полезно, ако новият проблем е по-прост от първоначалния или има по-добри свойства, или има известен метод за решение за него, или може би готова програма.
Пример 3.13. Еквивалентно преобразуване на квадратното уравнение във форма (избиране на пълен квадрат) свежда проблема до проблема за изчисляване на квадратния корен и води до формули (3.2), известни със своите корени.
Еквивалентните трансформации понякога позволяват да се намали решението на първоначалния изчислителен проблем до решението на изчислителен проблем от напълно различен тип.
Пример 3.14. Проблемът за намиране на корена на нелинейно уравнение може да се сведе до еквивалентния проблем за намиране на глобалната минимална точка на функцията. Действително функцията е неотрицателна и достига минимална стойност, равна на нула за тези и само тези x, за които
2. Апроксимационни методи.
Тези методи позволяват да се апроксимира (приближи) първоначалната задача с друга, чието решение е в известен смисъл близко до решението на първоначалната задача. Грешката, произтичаща от такава замяна, се нарича апроксимационна грешка. Като правило проблемът с приближението съдържа някои параметри, които ви позволяват да регулирате големината на грешката на приближението или да повлияете на други свойства на проблема. Прието е да се казва, че методът на приближение се сближава, ако грешката на приближението клони към нула, тъй като параметрите на метода клонят към определена гранична стойност.
Пример 3.15. Един от най-простите начини за изчисляване на интеграла е да се приближи интеграл въз основа на формулата за правоъгълници с размер
Стъпката тук е параметър на метода. Тъй като това е специално конструирана интегрална сума, от дефиницията на определен интеграл следва, че когато методът на правоъгълника се сближава,
Пример 3.16. Като вземете предвид дефиницията на производната на функция, за нейното приблизително изчисление можете да използвате формулата. Приблизителната грешка на тази формула за числено диференциране клони към нула, когато
Един от често срещаните методи за приближение е дискретизацията - приблизителна замяна на първоначалния проблем с крайномерен проблем, т.е. проблем, чиито входни данни и желано решение могат да бъдат уникално определени от краен набор от числа. За задачи, които не са крайномерни, тази стъпка е необходима за последваща реализация на компютър, тъй като компютърът може да работи само с краен брой числа. В примери 3.15 и 3.16 по-горе беше използвано вземане на проби. Въпреки че точното изчисление на интеграла включва използването на безкраен брой стойности (за всички, неговата приблизителна стойност може да бъде изчислена с помощта на краен брой стойности в точки а). По същия начин, проблемът с изчисляването на производната, чието точно решение включва операцията за преминаване към границата при (и следователно използването на безкраен брой стойности на функцията се свежда до приблизително изчисление на производната по отношение на две стойности на функцията.
При решаването на нелинейни проблеми широко се използват различни методи за линеаризация, които се състоят в приблизителна замяна на първоначалния проблем с по-прости линейни задачи. Пример 3.17. Нека е необходимо да се изчисли приблизително стойността за на компютър, способен да извършва прости аритметични операции. Обърнете внимание, че по дефиниция x е положителен корен на нелинейно уравнение. Нека има някакво известно приближение на Нека заменим параболата с права линия, която е допирателна, начертана към нея при
точка с абсцисата. Пресечната точка на тази допирателна с оста дава по-добро приближение и се намира от линейно уравнение. Решавайки го, получаваме приблизителна формула
Например, ако вземете за, получавате прецизирана стойност
При решаването на различни класове изчислителни задачи могат да се използват различни методи на приближение; Те включват методи за регулиране на решението на неправилно поставени проблеми. Обърнете внимание, че методите за регулиране се използват широко за решаване на лошо обусловени проблеми.
3. Директни методи.
Методът за решаване на задача се нарича директен, ако позволява да се получи решение след извършване на краен брой елементарни операции.
Пример 3.18. Методът за изчисляване на корените на квадратно уравнение с помощта на формули е директен метод. Тук се считат за елементарни четирите аритметични операции и операцията за квадратен корен.
Имайте предвид, че елементарна операция на директния метод може да бъде доста сложна (изчисляване на стойностите на елементарна или специална функция, решаване на система от линейни алгебрични уравнения, изчисляване на определен интеграл и т.н.). Фактът, че се приема като елементарен, във всеки случай предполага, че прилагането му е значително по-просто от изчисляването на решението на целия проблем.
При конструирането на директни методи се обръща значително внимание на минимизирането на броя на елементарните операции.
Пример 3.19 (диаграма на Хорнер). Нека задачата е да се изчисли стойността на полином
според зададените коефициенти и стойността на аргумента x. Ако изчислите полинома директно с помощта на формула (3.12) и го намерите чрез последователно умножение по x, тогава ще трябва да извършите операции за умножение и събиране.
Много по-икономичен метод за изчисление се нарича схема на Хорнер. Базира се на запис на полином в следната еквивалентна форма:
Поставянето на скоби диктува следния ред на изчисленията: Тук изчисляването на стойността изисква извършване само на операции за умножение и събиране.
Схемата на Хорнер е интересна, защото дава пример за метод, който е оптимален по отношение на броя на елементарните операции. Като цяло стойност не може да бъде получена по никакъв метод в резултат на извършване на по-малко операции на умножение и събиране.
Понякога директните методи се наричат точни, което означава, че ако няма грешки във входните данни и ако елементарните операции се изпълняват точно, полученият резултат също ще бъде точен. Но при внедряване на метода на компютър е неизбежна появата на изчислителна грешка, чиято големина зависи от чувствителността на метода към грешки при закръгляване. Много директни (точни) методи, разработени в предмашинния период, се оказаха неподходящи за машинни изчисления именно поради прекомерната чувствителност към грешки при закръгляване. Не всички точни методи са такива, но си струва да се отбележи, че не съвсем успешният термин „точен“ характеризира свойствата на идеалното изпълнение на метода, но не и качеството на резултата, получен от реални изчисления.
4. Итеративни методи.
Това са специални методи за конструиране на последователни приближения към решаването на задача. Прилагането на метода започва с избора на едно или няколко начални приближения. За да се получи всяко от следващите приближения, се извършва подобен набор от действия, като се използват предварително намерените приближения - итерация. Неограниченото продължение на този итеративен процес теоретично ни позволява да конструираме безкрайна последователност от приближения към решението
итерационна последователност. Ако тази последователност се сближава до решение на проблема, тогава се казва, че итеративният метод се сближава. Наборът от начални приближения, за които методът се сближава, се нарича област на сближаване на метода.
Обърнете внимание, че итеративните методи се използват широко при решаването на голямо разнообразие от проблеми с помощта на компютри.
Пример 3.20. Нека разгледаме добре познатия итеративен метод, предназначен за изчисляване (където методът на Нютон. Нека зададем произволно първоначално приближение. Изчисляваме следващото приближение, използвайки формулата, получена с помощта на метода на линеаризация в пример 3.17 (вижте формула (3.11)). Продължавайки този процес освен това получаваме итеративна последователност, в която следващото приближение се изчислява с помощта на рекурентната формула
Известно е, че този метод се сближава при всяко първоначално приближение, така че неговата област на сближаване е множеството от всички положителни числа.
Нека го използваме, за да изчислим стойността на -битов десетичен компютър. Да зададем (както в пример 3.17). Тогава по-нататъшните изчисления са безсмислени, тъй като поради ограничения характер на битовата решетка, всички последващи уточнения ще дадат същия резултат. Сравнението с точната стойност обаче показва, че още при третата итерация са получени 6 правилни значими цифри.
Използвайки метода на Нютон като пример, ще обсъдим някои типични проблеми за итеративните методи (и не само за тях). Итеративните методи по своята същност са приблизителни; нито едно от получените приближения не е точната стойност на решението. Въпреки това, методът на конвергентна итерация дава възможност по принцип да се намери решение с произволна точност.Следователно, когато се използва итеративният метод, изискваната точност винаги е посочена и итерационният процес се прекъсва веднага щом бъде постигната.
Въпреки че фактът, че методът конвергира, със сигурност е важен, той не е достатъчен, за да се препоръча методът за използване на практика. Ако методът се сближава много бавно (например, за да получите решение с точност от 1%, трябва да направите итерации), тогава той е неподходящ за компютърни изчисления. Бързо конвергентните методи, които включват метода на Нютон, имат практическа стойност (припомнете си, че точността на изчислението беше постигната само с три итерации). За теоретично изследване на скоростта на конвергенция и условията на приложимост на итеративните методи се извеждат така наречените априорни оценки на грешката, които позволяват да се даде известно заключение за качеството на метода дори преди изчисленията.
Нека представим две такива априорни оценки за метода на Нютон. Нека се знае, че тогава за всички и грешките на две последователни приближения са свързани със следното неравенство:
Ето стойност, характеризираща относителната грешка на приближението. Това неравенство показва много висока квадратична степен на сходимост на метода: при всяка итерация „грешката“ се повдига на квадрат. Ако го изразим чрез грешката на първоначалното приближение, получаваме неравенството
от което е ролята на добрия избор на начално приближение. Колкото по-малка е стойността, толкова по-бързо ще се сближи методът.
Практическата реализация на итеративните методи винаги е свързана с необходимостта от избор на критерий за завършване на итеративния процес. Изчисленията не могат да продължат безкрайно и трябва да бъдат прекъснати в съответствие с някакъв критерий, свързан например с постигане на дадена точност. Използването на априорни оценки за тази цел най-често се оказва невъзможно или неефективно. Въпреки че качествено правилно описват поведението на метода, такива оценки са надценени и предоставят много ненадеждна количествена информация. Често априорните оценки съдържат неизвестни
количества (например оценките (3.14), (3.15) съдържат количеството a), или предполагат наличието и сериозното използване на някаква допълнителна информация за решението. Най-често такава информация не е налична и нейното получаване е свързано с необходимостта от решаване на допълнителни проблеми, често по-сложни от първоначалния.
За да се формира критерий за прекратяване при постигане на дадена точност, като правило се използват така наречените апостериорни оценки на грешката - неравенства, при които големината на грешката се оценява чрез известни стойности или стойности, получени по време на изчислителния процес. Въпреки че такива оценки не могат да се използват преди началото на изчисленията, те осигуряват конкретно количествено определяне на несигурността по време на процеса на изчисление.
Например за метода на Нютон (3.13) е валидна следната апостериорна оценка:
С. Улам използва произволни числа, за да симулира компютърно поведението на неутроните в ядрен реактор. Тези методи могат да бъдат незаменими при моделиране на големи системи, но тяхното подробно представяне включва значително използване на апарата на теорията на вероятностите и математическата статистика и е извън обхвата на тази книга.
