Численные методы

МЕТОДИРОЗВ’ЯЗАННЯСИСТЕМ ЛІНІЙНИХАЛГЕБРАЇЧНИХРІВНЯНЬ.

Розглянемочисельні методирозв’язаннясистем лінійнихалгебраїчнихрівнянь

Ax=f T (1)

де A-матриця m*m, x=(x1,x2,...,xm)-шуканий вектор,

f=(f1,f2,... , fm)-заданий вектор.

Припускаємо,що

тавизначникматриці Авідмінний віднуля, так щоіснує єдинийрозв’язок х.З курсу алгебривідомо,щосистему(1)можна розв’язатиза формуламиКрамера*. Длявеликих mцейспосіб практичнонереалізованийтому,що потребуєпорядку m!aрифметичнихдій. Тому широковикористовуютьсяінші методирозв’язання,наприклад,метод Гаусса**,який потребує

дій.

Методичисельногорозв’язаннясистеми (1)поділяютьсяна дві групи:

-пряміметоди;

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

Упрямих(або точних)методах розв’язокxсистеми(1) відшукуєтьсяза скінченнукількістьарифметичнихдій.Внаслідокпохибок заокругленняпрямі методинасправді неприводять доточного розв’язкусистеми (1) і назватиїх точнимиможливо лишезалишаючиосторонь похибкизаокруглення.

Ітераційніметоди(їх також називаютьметодами послідовнихнаближень)полягаютьу тому, що розв’язокxсистеми (1) відшукуєтьсяяк границя при

послідовнихнаближень

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

______________________

* Крамер Габрієль(1704-1752)- швейцарськийматематик.

** ГаусКарл Фридрих(1777-1855)- німецькийматематик,астроном, фізик,геодезист,професорГетінгенськогоуніверситету.

МЕТОД ГАУССА .

Запишемосистему (1) урозгорнутомувигляді:

а11x1+a12x2+...+a1mxm=f1,

a21x1+a22x2+...+a2mxm=f2 , (2)

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

am1x1+am2x2+...+ammxm=fm.

МетодГаусса розв’язаннясистеми (2) полягаєу послідовномувилученніневідомих x1,x2,..., xm-1 з цієї системи.

Припустимо,що a11

0. Поділив першерівняння наa11,одержимо

x1+c12x2+...+c1mxm=y1 , (3)

де:c1j=a1j/a11; j=2,m ; y1=f1/a11.

Розглянемотепер рівняннясистеми (2), щозалишилися

ai1x1+ai2x2+...+aimxm=fi ; i= 2,m . (4)

Помножимо (3) на ai1 та віднімемоодержане рівнянняз і-го рівняннясистеми(4),i=2,m.

У результатіодержимо наступнусистему рівнянь:

x1+c12x2+...+c1jxj+...+c1mxm=y1,

(1) (1) (1) (1)

a22x2+...+a2jxj+...+a2mxm=f2,

............................................ (5)

(1) (1) (1) (1)

am2x2+...+amjxj+...+ammxm=fm.

Tутпозначено:

(1) (1)

aij=aij-c1jai1; fi=fi-y1ai1; i,j=2,m. (6)

Матрицясистеми (5) маєвигляд:

Матрицітакої стуктуризаведено позначатитак:

дехрестикамипозначеніненульовіелементи.

Усистемі (5) невідоме хміститьсятільки в першомурівнянні, томуу подальшомудостатньо матисправу із скороченоюсистемою рівнянь:

(1) (1) (1) (1)

a22x2+...+a2jxj+...+a2mxm=f2,

.............................................. (7)

(1) (1) (1) (1)

am2x2+...+amjxj+...+ammxm=fm .

Тимсамим ми здійснилиперший крокметоду Гаусса. Коли

,то з системи (7) зовсім аналогічноможна вилучити невідоме x2і прийти досистеми, еквівалентній(2),що має матрицютакої структури:

Прицьому першерівняння системи (5) залишаєтьсябез зміни.

Вилучаятаким же чиномневідомі х 3, х4,... ,xm-1,приходимоостаточно досистеми рівняньвиду:

x1+c12x2+...+c1,m-1xm-1+c1mxm=y1,

x2+...+c2,m-1xm-1+c2mxm=y2,

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

xm-1+cm-1,mxm=ym-1,

xm=ym ,

щоеквівалентнапочатковійсистемі (2) .

Матрицяцієї системи

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

Побудовасистеми (8) складаєпрямийхід методу Гаусса.Зворотнiйхід полягаєу відшуканніневідомих х1,... ,хm зсистеми (8). Томущо матрицясистеми маєтрикутнийвигляд, можнапослідовно,починаючи зхm,відшукативсі невідомі.Дійсно, xm=ym,

x m-1=ym-1 -cm-1,mx m iт.д.

Загальніформи зворотньогоходу маютьвигляд:

xi=yi- еcijxj; i=m-1,1; xm=ym. (10)

j=i+1

Приреалізаціїна ЕОМ прямогоходу методуГаусса немаєнеобхідностідіяти із змінними x1,x2,... ,xm.Досить вказатиалгоритм,заяким початковаматриця Аперетворюєтьсядо трикутноговигляду (9),тавказати відповіднеперетворенняправих частинсистеми.

Одержимоці загальніформули.

Нехайвже здійсненіперші к-1кроків, тобтовже вилученізмінні

x1, x2,...,xk-1.

Тодімаємо систему:

x1+c12x2+...+c1,k-1xk-1+c1kxk+....+c1mxm=y1,

x2+...+c2,k-1xk-1+c2kxk+....+c2mxm=y2,

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

xk-1+ck-1,kxk+...+ck-1,mxm=yk-1, (11)

(k-1) (k-1) (k-1)

akkxk+...+akmxm=fk,

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

(k-1) (k-1) (k-1)

amkxk+...+ammxm=fm.

Розглянемо К-терівняння цієїсистеми:

(k-1) (k-1) (k-1)

akkxk+...+akmxm=fk ,

таприпустимо,що

. Поділившиобидві частиницього рівнянняна

,одержимо

xk+ck,k+1xk+1+...+ckmxm=yk , (12)

(k-1) (k-1) (k-1) (k-1)

де ckj=akj/akk; j=k+1,m ; yk=fk / akk .

Даліпомножиморівняння (12) на

та віднімемоодержанеспіввідношенняз i-горівняння системи(11). У результатіостання групарівнянь системи(11) набуває наступноговигляду:

xk+ck,k+1xk+1+...+ ckmxm=yk,

(k) (k) (k)

ak+1,k+1xk+1+...+ak+1,mxm=fk+1,

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

(k) (k) (k)

am,k+1xk+1+...+ ammxm=fm,

(k) (k-1) (k-1) (k) (k-1) (k-1)

де:aij=aij - aikckj ; i,j=k+1,m ; fi=fi - aikyk ; i=k+1,m .

Такимчином, у прямомуході методуГаусса коефіцієнтирівнянь перетворюютьсяза наступнимправилом

(0)

akj=akj; k,j=1,m ;

(k-1) (k-1)

ckj=akj /akk; j=k+1,m ; k=1,m ; (13)

(k) (k-1) (k-1)

aij=aij -aikckj ; i,j=k+1,m ; k=1,m . (14)

Обчисленняправих частинсистеми (8) здійснюєтьсяза формулами:

(0) (k-1) (k-1)

fk=fk ; yk= fk /akk ; k=1,m ; (15)

(k) (k-1) (k-1)

fi=fi - aikyk; k=1,m . (16)

Коефіціентиcij і праві частини yi; i=1,m;j=i+1,m зберігаютьсяу пам’яті ЕОМі використовуютьсяприздійсненнізворотньогоходу за формулами(10).

Основнимобмеженнямметоду є припущення,що усі елементи

,на які здійснюєтьсяділення, відрізняютьсявід нуля. Число

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

, а інше число( тобто на К-мукроці вилучаєтьсяне xk,а інша зміннаxj,

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

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

1.Обчисленнякоефіцієнтів

за формулами(13) потребує:

(m-k)=1+2+...+(m-1)=

ділень.

2.Обчисленняусіх коефіцієнтів

за формулами(14) потребує

множень(тут ми використовуємолегко перевіряємуза індукцієюрівність

Такимчином, обчисленняненульовихелементів

трикутноїматриці С потребує

операціймноження іділення.

3.Обчисленняправих частинyk за формулами (15) потребує m

ділень, авідшукання

за формулами(16)

множень.Разом, обчисленняправих частинперетвореноїсистеми (8) потребує

діймноження іділення.

Усьогодля реалізаціїпрямого ходуметоду Гауссанеобхідновиконати

дій.

4.Дляреалізаціїзворотньогоходу методуГаусса за формулами(10) необхідно

множень.

Всього,для реалізаціїметоду Гауссанеобхідновиконати

діймноження іділення, причомуосновний часвитрачаєтьсяна прямий хід.Для великих m числодій множенняі ділення уметоді Гауссаблизьке до

За витратамичасу та необхідніймашинній пам’ятіметод Гауссапридатний длярозв’язаннясистем рівнянь(2) загальноговигляду з кількістюзмінних m порядку100.

ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ.

Пустьимеется функция

которую необходимопродифференцироватьнесколько рази найти этупроизводнуюв некоторойточке.

Если заданявный вид функции, то выражениедля производнойчасто оказываетсядостаточносложным и желательноего заменитьболее простым.Если же функциязадана тольков некоторыхточках (таблично),то получитьявный вид еепроизводныхввобще невозможно.В этих ситуацияхвозникаетнеобходимостьприближенного(численного)дифференцирования.

Простейшаяидея численногодифференцированиясостоит в том,что функциязаменяетсяинтерполяционныммногочленом(Лагранжа, Ньютона)и производнаяфункции приближенногозаменяетсясоответствующейпроизводнойинтерполяционногомногочлена

Рассмотрим простейшиеформулы численногодифференцирования, которые получаютсяуказаннымспособом.

Будем предполагать,что функциязадана в равностоящихузлах

Еезначения изначения производныхв узлах будемобозначать

Пустьфункция заданав двух точках

ее значения

Посстроим интерполяционный многочленпервой степени

Производная

равна

Производнуюфункцию

в точке

приближеннозаменяем производнойинтерполяционногомногочлена

(1)

Величина

называется первойразностнойпроизводной.

Пусть

задана в трехточках

ИнтерполяционныймногочленНьютона второйстепени имеетвид

Берем производную

В точке

она равна

Получаемприближеннуюформулу

(2)

Величина

называется центральной разностнойпроизводной.

Наконец, есливзять вторуюпроизводную

получаемприближеннуюформулу.

(3)

Величина

называется второйразностнойпроизводной.

Формулы(1)-(3) называютсяформуламичисленногодифференцирования.

Предполагаяфункцию

достаточноечисло раз непрерывнодифференцируемой,получим погрешностиприближенныхформул (1)-(3).

В дальнейшемнам понадобитсяследующая лемма.

Лемма 1.Пусть

произвольныеточки,

Тогда существуеттакая точка

что

Доказательство. Очевидно неравенство

По теоремеБольцано-Кошио промежуточныхзначенияхнепрерывнойфункции назамкнутомотрезке онапринимает всезначения между

Значит существуеттакая точка

что выполняетуказанное влемме равенство.

Погрешностиформул численногодифференцированиядает следующаялемма.

Лемма 2.

1.Предположим,что

Тогда существуеттакая точка

, что

(4)

Если

то существует такая точка
, что

(5)

Когда

то существует
такая, что

(6) Доказательство.По формулеТейлора

откуда следует (4).

Если

то по формулеТейлора

(7)

где

Подставим(7) в

Получаем

Заменяя всоответствиис леммою 1

получаем

Откуда иследует (6).

Равенство(5) доказываетсяаналогично( доказательствопровестисамостоятельно).

Формулы(4)-(6) называютсяформулами численногодифференцированияс остаточнымичленами.

Погрешностиформул (1)-(3) оцениваютсяс помощью следующихнеравенств,которые вытекаютиз соотношений(4)-(6):

Говорят,что погрешностьформулы (1) имеетпервыйпорядок относительно

(или порядка

), а погрешностьформул (2) и (3) имеет второйпорядок относительно

(или порядка

). Также говорят,что формулачисленногодифференцирования(1) первогопорядка точности(относительно

),а формулы (2) и(3) имеют второйпорядок точности.

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

Выбороптимальногошага. Допустим,что границаабсолютнойпогрешностипри вычислениифункции

в каждой точкеудовлетворяетнеравенству

(8)

Пусть внекоторойокрестноститочки

производные,через которыевыражаютсяостаточныечлены в формулах(5), (6), непрерывны и удовлетворяютнеравенствам

(9)

где

- некоторыечисла. Тогдаполная погрешностьформул (2), (3) (безучета погрешностейокругления)в соответствиис (5), (6), (8), (9)не превосходитсоответственновеличин

Минимизацияпо

этих величинприводит кследующимзначениям

(12)

при этом

(13)

Если привыбранном длякакой-либо изформул (2), (3) значении

отрезок

не выходит запределы окрестности точки

,в которой выполняетсясоответствующеенеравенство(9), то найденное

есть оптимальными полная погрешностьчисленногодифференцированияоцениваетсясоответствующейвеличиной (13).

ИНТЕРПОЛИРОВАНИЕ СПЛАЙНАМИ.

ИнтерполированиемногочленомЛагранжа илиНьютона наотрезке

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

разбивают начастичныеотрезки и накаждом из частичныхотрезков приближеннозаменяют функцию

многочленомневысокойстепени ( такназываемаякусочно-полиномиальнаяинтерполяция).

Однимиз способовинтерполяциина всем отрезкеявляетсяинтерполированиес помощьюсплайн-функций.Сплайн-функциейили сплайном называюткусочно-полиномиальнуюфункцию, определеннуюна отрезке

и имеющую наэтом отрезкенекоторое числонепрерывныхпроизводных.

Слово,,сплайн’’(английскоеspline)означает гибкуюлинейку, используемуюдля проведениягладких кривыхчерез заданныеточки плоскости.

Преимуществосплайнов передобычной интерполяциейявляется, во-первых,их сходимость,и, во-вторых,устойчивостьпроцесса вычислений.

Рассмотримчастный, нораспространенныйв вычислительнойпрактике случай,когда сплайнопределяетсяс помощью многочленовтретьей степени( кубическийсплайн).

Пустьна

задана непрерывнаяфункция

.Введем узлы ( сетку):

и обозначим

Интерполяционнымкубическимсплайном,соответствующимданной функции

и данным узлам,называетьсяфункция

,удовлетворяющаяследующимусовиям:

а) на кождомсегменте

функция

является многочленомтретьей степени;

б) функция

,а так же ее перваяи вторая производныенепрерывнына

;

в)

Последнееусловие называетсяусловиеминтерполирования.

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

На каждомиз отрезков

будем искатьфункцию

в виде многочленатретьей степени

(1)

где

- коэффициенты, подлежащиеопределению.Выясним смыслвведенныхкоэффициентов.Имеем

поэтому

Из условий интерполирования

получаем, что

Доопределим, кроме того ,

Далее, требованиенепрерывностифункции

приводит к условиям

Отсюда,учитываявыражения дляфункций

получаем при

уравнения

Обозначая

перепишем этиуравнения ввиде

(2)

Условиянепрерывностипервой производной

приводятк уравнениям

(3)

Из условий непрерывностивторой производнойполучаем уравнения

. (4)

Объединяя(2) -(4) , получим систему

уравненийотносительно

неизвестных

Два недостающихусловия получают,задавая те илииные граничныеусловия для

Предположим,например, чтофункция

удовлетворяетусловиям

Тогда естественнотребовать,чтобы

Отсюда получаем

т.е.

Заметим,что условие

совпадает суравнением (4) при

.Таким образом,приходим кзамкнутойсистеме уравненийдля определениякоэффициентовкубическогосплайна:

Убедимсяв том, что этасистема имеетединственноерешение. Исключимиз (5)- (7) переменные

и получим систему,содержащуютолько

Для этого рассмотрим два соседнихуравнения (7) :

и вычтем второе уравнениеиз первого.Тогдаполучим

Подставляянайденноевыражение для

в правую частьуравнения (6),получим

(8)

Далее, из уравнения (5) получаем

И подставляяэти выраженияв (8) , приходимк уравнению

Окончательнодля определениякоэффициентов

получаем систему уравнений

(9)

В силудиагональногопреобладаниясистема (9) имеетединственноерешение. Таккак матрицасистемы трехдиагональная,решение можнонайти методомпрогонки. Понайденнымкоэффициентам

коэффициенты

определяютсяс помощь явныхформул

(10)

Такимобразом, доказано,что существуетединственныйкубическийсплайн, определяемыйусловиями а)-в) и граничнымиусловиями

Заметим , чтоможно рассматриватьи другие граничные условия.

ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ.

На практикередко удаетсявычислить точноопределенный интеграл. Например,в элементарныхфункциях невычисляетсяфункция Лапласа

широко используемаяв теории вероятностейдля вычислениявероятностей,связанных снормальнораспределеннымислучайнымивеличинами.

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

Квадратурныеформулы.

Введем понятиеквадратурные формулы. Пустьдан определенныйинтеграл

(1)

от непрерывнойна отрезке

функции

. Приближенноенеравенство

(2)

где

- некоторыечисла,

- некотрые точкиотрезка

, называетсяквадратурнойформулой, определяемой весами

и узлами

Говорят, чтоквадратурнаяформула точнадля многочленовстепени

, если при замене

на произвольныйалгебраическиймногочленстепени

приближенноеравенство (2)становитсяточным.

Рассмотримнаиболее простые квадратурныеформулы.

Формулапрямоугольников.Допустим, что

. Положим приближенно

(3)

где

,т.е. площадькриволинейнойтрапеции,ограниченнойсверху графикомфункции

,аппроксимируетсяплощадьюпрямоугольника,высота которогоравна значению

в средней точкеоснованиятрапеции .

Найдем остаточныйчлен , т.е. погрешностьформулы (3) .

Пусть

(4)

Так как

то согласноформуле Тейлорас остаточнымчленом в формеЛагранжа имеем

(5)

где

-некоторыеточки ,

Функция

являетсяпервообразнойдля

Поэтому дляинтеграла,стоящего влевой частиприближенногоравенства (3),из формулыНьтона - Лейбницас расчетом (5)вытекает следующеесоотношеие

Отсюдас помощью ранеедоказаннойлеммы получаемформулупрямоугольниковс остаточнымчленом :

(6)

Формулатрапеций.Пусть

Полагаем

(7)

где

т.е. интеграл

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

Найдемостаточныйчлен, т.е. погрешностьформулы (7). Выразим

где

- функция (4), поформуле Тейлорас остаточнымчленом в интегральнойформе

(8)

(9)

Согласно(8) имеем

(10)

Отделивв правой части(9) слагаемое

и заменив еговыражением(10), с учетом того,что

находим

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

* ФормулаТейлора с остаточнымчленом в интегральнойформе

Теорема1 (обобщеннаятеорема о среднем).Пусть

причем

на

Тогда существуеттакая точка

что

Доказательство.Положим

(11)

Тогд, так как

то

и, следовательно,

Если

то

и в качестве

можн взятьлюбую точкуиз

Если

то вытекаетсуществованиетакого числас,удовлетворяющего неравенствам ( для этого делимвсе части

на

(12)

что

(13)

По теоремео промежуточныхзначенияхнепрерывнойфункции в силу(11) , (12) найдетсяточка

, в которой

что вместе сравенством(13) доказываеттеорему .

Теперь,так как

то по доказанной теоремою

где

- некотораяточка . Подставляяполученноев

,приходим к формулетрапеций состаточнымчленом :

(14)

ФормулаСимпсона .Предположим,что

Интеграл

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

де

Указаннаяпарабола задаетсяуравнением

в чемнетрудно убедиться,положив поочередно

(ее можно такжеполучить, построивинтерполяционныймногочленвторой степении приводя подобные)Отсюда находи( проверитьсамостоятельно)

Такимобразом , формулаСимпсона ,называемаятакже формулойпарабол ,имеет вид

(15)

Положим

где

-функция(4). Поскольку

то согласноформул Тейлорас остаточнымчленом в интегральнойформе имеем

Отсюдаполучаем

(16)

т.к. остальныечлены взаимноуничтожаются.

Поскольку

то применяяк интегралу(16) теорему 1 , азатем к полученномурезультатулемму, находим

(17)

где

нектрые точки.

Принимаяво внимание,что

из (16), (17) приходимк формуле

(18) т.е. к формулеСимпсона состаточнымчленом.

Рассмотримквадратурныеформулы прямоугольников(3), трапеций (7) иСимпсона (15)называютсяканоничными.

Усложненныеквадратурныеформулы.

На практике, если требуетсявычислитьприближенноинтеграл (1) , обычноделят заданныйотрезок

на

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

называетсяусложненной.При примененииформул прямугольникови трапецийдлину частичныхотрезков удобноприменять за

, а при использованииформулы Симпсона- за

Остановимсясначала напримененииформулы прямоугольников.Пусть

Обозначимчастичныеотрезки через

где

В соответствии с (3) полагаем

(19)

где

значение

в серединечастичногоотрезка

.При этом справедливоаналогичное(6) равенство

(20) где

некотораяточка.

Суммирование по всем частичнымотрезкамприближенногоравенства (19)приводит кусложненнойквадратурнойформуле прямоугольников:

(21)

а суммированиеравенств (20) сучетом того,чтопо лемме

где

-некотораяточка отрезка

,дает усложненнуюформулу прямоугольниковс остаточным членом:

(22)

Совершенноаналогичноприуслвии, что

с использованиемформул (7), (14) получаетсяусложненнаяквадратурнаяформула трапеций

(23)

и отвечающаяей формула состаточнымчленом

(24)

где

некотораяточка.

Пустьтеперь

и, как обычно,

Перепишем каноническуюквадратурнуюформулу Симпсона (15) применительнок отрезку

длины

Суммируялевую и правуючасти этогосоотношенияот 0 до

N-1,получаем усложненную квадратурнуюформулу Симпсона (25)

Сответствующаяей формула состаточнымчленом, полученнаясуммированиемпо частичнымотрезкам

равенств вида(18), при условии,что

,такова :

(26)

где

Введем краткиеобозначения

(27)

где

а также положим

(28)

где

Приближенныеравенства

(29)

(30)

назовемсответственно формуламипрямоугольников,трапеций иформулой Симпсона,опуская слова‘’усложненнаяквадратурная’’.

Из вираженийостаточныхчленов в (22), (24), (26)видно, что формулы(29) прямоугольников трапеций точныдля многочленовпервой степени,т.е. для линейныхфункций, а формула(30) Симпсона точнадля многочленовтретьей степени(для них остаточныйчлен равен нулю). Погрешностьформул (29) имеетвторой порядокотносительно

(заведомо нелучше, если

непрерывнана

и не обращаетсяв нуль), а формулаСимпсона присоответствующейгладкости

является формулойчетвертогопорядка точности.Поэтму дляфункций класса

при малом

формула Симпсонаобычно даетболее высокуюточность, чемформула (29).

Погрешностьформулы прямугольникови формулы Симпсонапри вычисленииинтеграла (1) всилу (22), (26) удовлетворяетнеравенствам

(31)

(32)

Аналогичноенеравенствоимеет местои для погрешностиформули трапеций.

Наряду соценками погрешносисверху полезныоценки снизу.В частности,для погрешностиформулы прямоугольниковоценка снизу,вытекающаяиз (22), такова:

(33)

Пример.Исследоватьпогрешностьквадратурныхформул дляинтеграла

при

Имеем

на

Согласно(31)-(33) получаем

Формулыпрямоугольников трапеций вотдельностиуступают приинтегрированиигладких функцийформуле Симпсона.Однако в пареони обладаютценным качеством,а именно, если

не изменяетзнака на

то формулы (29)дают двусторонниеприближениядля интеграла(1), так как согласно(22), (24) их остаточныечлены имеютпротивоположныезнаки.

В рассмотренномпримере

Поэтому

В даннойситуации естественноположить

Тогда

т.е. погрешностьоцениваетсячерез самые приближенные значения интеграла.

УМОВИЗАСТОСУВАННЯМЕТОДУ ГАУССА.

Ранішбуло показано,що метод Гауссаперетворюєвихідну системурівнянь

(1)

до еквівалентноїсистеми

,(2)

де С-верхня трикутнаматриця з одиницямина головнїйдіагоналі.З’ясуємо тепер,як зв’язанi міжсобою векториправих частинfта y.

Ранішми переконалися,що праві частинисистеми (2) обчислюютьсяза формулами

З цихспіввідношеньможна послідовноодержати

, (3)

де

-числовікоефіцієнти,причому

Співвідношення(3) можна записатиу матричномувигляді

,(4)

де B-нижня трикутнаматриця з елементами

на головнійдіагоналі.

Нагадаємо,що головнеприпущенняпри формуліровціметоду Гауссаполягало утому, що усі

Тому на діагоналіматриці Встоять ненульовіелементи,

,тобтоВ маєобернену, a

.Підставляючиостаннє у (2),приходимо дорівняння

звідки

. (5)

Порівнюючи(5) з рівнянням(1), приходимодо висновку,що як наслідокзастосуванняметоду Гауссаодержане розкладаннявихідної матриці Ау добуток A=BC, де В-нижня трикутнаматриця з ненульовимиелементамина головнійдіагоналі,С-верхнятрикутна матрицяз одиничноюголовною діагоналлю.

Заразможно тлумачитиметод Гауссатаким чином.Нехай заданоматрицю Aі векторf.Спочатку утворюєтьсярозклад Ау добуток двохтрикутнихматриць

.Далі послідовнорозв’язуютьсядві системирівнянь

(6)

(7)

з трикутнимиматрицями,звідки і одержуєтьсяшуканий векторx.Розклад А=ВСвідповідаєпрямій ходіметоду Гаусса,а розв’язаннясистеми (6)- (7)- зворотній ході.Зауважимо, щоу наведеномураніш алгоритмірозклад A=BCтарозв’язаннясистеми (6) провадитьсяодночасно.

Водночасз сказаногоможна зробитинаступнийвисновок. Томущо

то методГаусса дозволяєодночасно зров’язанннямсистеми (1) обчислитивизначникматриці Апростим множеннямведучих елементів.Коли ж задачеює просто обчисленнявизначникаматриці, то цеможна зробитиметодом Гаусса,при цьому немаєнеобхідностіобчислюватиправі частиниперетворюємихрівнянь.

Далі,додержуючисьстандартнихпозначень,нижні трикутніматриці будемопозначати L(від англійського lower- нижній), таверхні трикутні- літерою U (віданглійськогоupper-верхній).

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

-кутовиймінор порядкуj матриціА, тобто

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

Теоремапро LU-розклад.Нехай усі кутовімінори матриціАвідмінні віднуля,

.Тоді матрицюАможна податиєдиним чиному вигляді добутка

А=LU , (8)

де L-нижня трикутнаматриця з ненульовимидіагональнимиелементамиі U -верхня трикутнаматриця з одиничноюголовною діагоналлю.

Доведення.Доведемосформульованетвердженняспочатку дляматриць другогопорядку. Будемошукати розкладматриці

у вигляді

де

-невідомі досічисла. Для відшуканняцих чисел маємосистему рівнянь:

яка маєєдиний розвязок

За припущенням теореми

,тобто елементи

та

відмінні віднуля.

Подальшедоведенняпроведемометодом математичноїіндукції. Нехайтвердженнявірне для матрицьпорядку

доведемо,що воно вірнеі для матрицьпорядку к.

Подамоматрицю Апорядку Ку вигляді

(9)

та позначимо

;

Згідноз умовами теореми

і тоді за припущеннямиіндукції існуєрозклад матриці

;

де

-відповідно нижня і верхнятрикутні матриці,що володіютьвказаними утеоремі властивостями.Будемо шукатирозклад матриці(9) у вигляді

, (10)

де

-невідомі досівектори.

Помножимоматриці в правійчастині рівняння(10) і, враховуючи(9), приходимодо системирівнянь

;(11)

;(12)

;(13)

З припущеннняіндукції виходитьіснуванняматриць

;

.Тому з (11) і (12) одержуємо

;

і,далі,з (13)

Такимчином,

-розкладматриці А існує.З розкладу (10)виходить, що

За умовамитеореми

,а за припущеннямиіндукції

,і тому

.Тим самим індукціязавершена ідоведена можливістьшуканого розкладу.

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

Тоді

. (14)

Матрицяу лівій частинірівняння (14) єверхньою трикутною,а в правій частині- нижньою трикутною.Така рівністьможлива лишеу випадку. якщоматриці

діагональні.Але на діагоналіматриці

(а тому і матриці

)стоять одиниці,отже ці матриціодиничні

Звідсиодержуємо

;

,тобто розклад(8) єдиний. Теоремаповністю доведена.

Зауважимо,що коли хочаб один з угловихмінорів матриціАдорівнювавнулеві, то вказаний

- розклад неможливий.Це легко побачитина прикладіматриць другогопорядку.

Висновок.Метод Гауссаможливо використовуватитоді, та й лишетоді, коли усікутові мінориматриці Авідмінні віднуля.

Булопоказано, щометод Гауссаприводить дорозкладу вихідноїматриці у добутокдвох трикутних.Більш детальноописати структуруцих трикутнихматриць можливоза допомогоютак званихелементарнихтрикутнихматриць.

Матриця

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

У матриці

усі елементиголовної діагоналіокрім

дорівнюютьодиниці. З рештиелементіввідміннимивід нуля можутьбути лише елементи

-гостовпчика, щорозташованінижче

.Оберненою до

є елементарнанижня трикутнаматриця

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

,що складаєтьсяз трьох рівнянь:

,(15)

Післяпершого крокувиключенняза методомГаусса перетворенасистема приймаєвигляд

,(16)

Звідсивидно, що матриця

системи (16) одержуєтьсяз вихідноїматриці Ашляхом множенняАзліва на елементарнуматрицю

(17)

так, що

.Прицьому систему(16) можна записатиу вигляді

Матрицю(17) будемо називатиелементарноютрикутноюматрицею, щовідповідаєпершому крокувиключенняметоду Гаусса.

Перепишемосистему (16) увигляді

,(18)

Здійснимодругий крокметоду Гаусса,тобто виключимоневідому

з останньогорівняння.

Тодіодержимо системувигляду

,(19)

Можнапереконатися,щоперехід від(18) до (19) здійснюєтьсязавдяки множеннясистеми (18) наелементарнутрикутну матрицю

.(20)

Такимчином,післядругого крокувиключенняприходимо досистеми

, (21)

де матриці

означені згідно(17), (20).

Нарешті,перемножаючи(21) на матрицю

одержимосистему

,(22)

матрицяякої

є верхньоютрикутноюматрицею зодиничноюголовною діагоналлю.

Звідкивиходить, зокрема,що A=LU,де

-нижнятрикутна матриця.

Такимчином,

-розклад матриціА може бути одержанийза допомогоюелементарнихтрикутнихматриць: спочаткубудуютьсяматриці

та обчислюється

,а потім відшукується

.Відзначимо,що матриці

мають простийвигляд

;

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

Записметоду Гауссау вигляді (22)детально описуєпроцес виключення.

Усе згаданераніш переноситьсябез виняткуна системирівнянь довільногопорядку (2).

Процесвиключенняможна записатиформулою

,(23)

де елементарнанижня трикутнаматриця

на к-мукроці виключеннямає вигляд

Матриця

здійснює виключенняневідомого

з рівнянь зномерамик+1, к+2, ... ,m.

Матриці

існують і маютьвигляд

МЕТОДГАУССА С ВЫБОРОМГЛАВНОГО ЭЛЕМЕНТА.

Основнаяидея метода.Может оказаться,что система

Ax=f (1)

имеетединственноерешение, хотякакой-либо изугловых миноровматрицы Аравен нулю. Вэтом случаеобычный методГаусса оказываетсянепригодным,но может бытьприменен методГаусса с выборомглавного элемента.

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

,то в процессевычисленийне будет происходитьделение нануль.

Различныеварианты методаГаусса с выборомглавного элементапроиллюстрируемна примересистемы из двухуравнений

(2)

Предположим,что

.Тогда на первомшаге будемисключатьпеременное

.Такой приемэквивалентентому, что система(2) переписываетсяв виде

(3)

и к (3) применяетсяпервый шагобычного методаГаусса. Указанныйспособ исключенияназываетсяметодомГаусса с выборомглавного элементапо строке.Он эквивалентенприменениюобычного методаГаусса к системе,в которой накаждом шагеисключенияпроводитсясоответствующаяперенумерацияпеременных.

Применяетсятакже методГаусса с выборомглавного элементапо столбцу.Предположим,что

. Перепишемсистему (2) ввиде

и к новойсистеме применимна первом шагеобычный методГаусса. Такимобразом, методГаусса с выборомглавного элементапо столбцуэквивалентенприменениюобычного методаГаусса к системе,в которой накаждом шагеисключенияпроводитсясоответствующаяперенумерацияуравнений.

Иногдаприменяетсяи методГаусса с выборомглавногоэлементаповсейматрице, когдав качествеведущего выбираетсямаксимальныйпо модулю элементсреди всехэлементовматрицы системы.

Матрицыперестановок.Ранее былопоказано, чтообычный методГаусса можнозаписать ввиде

где

-элементарныенижние треугольныематрицы. Чтобыполучить аналогичнуюзапись методаГаусса с выборомглавного элемента,необходиморассмотретьматрицы перестановок.

ОПРЕДЕЛЕНИЕ1.МатрицейперестановокРназываетсяквадратнаяматрица, у которойв каждой строкеи в каждом столбцетолько одинэлемент отличенот нуля и равенединице.

ОПРЕДЕЛЕНИЕ2.Элементарнойматрицей перестановок

называетсяматрица, полученнаяиз единичнойматрицы перестановкой

к-йи l-йстрок.

Например,элементарнымиматрицамиперестановоктретьего порядкаявляются матрицы

Можноотметить следующиесвойства элементарныхматриц перестановок,вытекающиенепосредственноиз ихопределения.

Произведениедвух (а следовательно,и любого числа)элементарныхматриц перестановокявляется матрицейперестановок(не обязательноэлементарной).
Для любойквадратнойматрицы Аматрица

отличаетсяот Аперестановкойк-йиl-йстрок.
Для любойквадратнойматрицы Аматрица

отличаетсяот Аперестановкойк-гои l-гостолбцов.

Применениеэлементарныхматриц перестановокдля описанияметода Гауссас выбором главногоэлемента постолбцу можнопояснить наследующемпримере системытретьего порядка:

(4)

Системаимеет вид (1), где

(5)

Максимальныйэлемент первогостолбца матрицыАнаходится вовторой строке.Поэтому надопоменять местамивторую и первуюстроки и перейтик эквивалентнойсистеме

(6)

Систему(6) можно записатьв виде

(7)

т.е. онаполучаетсяиз системы (4)путем умноженияна матрицу

перестановок

Далее,к системе (6) надоприменитьпервый шагобычного методаисключенияГаусса. Этотшаг эквивалентенумножениюсистемы (7) наэлементарнуюнижнюю треугольнуюматрицу

В результатеот системы (7)перейдем кэквивалентнойсистеме

(8)

или вразвернутомвиде

(9)

Из последнихдвух уравненийсистемы (9) надотеперь исключитьпеременное

.Посколькумаксимальнымэлементомпервого столбцаукороченнойсистемы

(10)

являетсяэлемент второйстроки, делаемв (10) перестановкустрок и темсамым от системы(9) переходим кэквивалентнойсистеме

(11)

которуюможно записатьв матричномвиде как

. (12)

Такимобразом система(12) получена из(8) применениемэлемен-тарнойматрицы перестановок

Далеек системе (11) надоприменитьвторой шагисключенияобычного методаГаусса. Этоэквивалентноумножениюсистемы (11) наэлементарнуюнижнюю треугольнуюматрицу

В результатеполучим систему

(13)

или

(14)

Заключительныйшаг прямогохода методаГаусса состоитв замене последнегоуравнениясистемы (14) уравнением

что эквивалентноумножению (13)на элементарнуюнижнюю треугольнуюматрицу

Такимобразом, длярассмотренногопримера процессисключенияГаусса с выборомглавного элементапо столбцузаписываетсяв

виде

(15)

По построениюматрица

(16)

являетсяверхней треугольнойматрицей сединичнойглавной диагональю.

Отличиеот обычногометода Гауссасостоит в том,что в качествесомножителейв (16) наряду сэлементарнымитреугольнымиматрицами

могутприсутствоватьэлементарныематрицы перестановок

Покажемеще, что из (16)следует разложение

PA=LU, (17)

где L-нижняятреугольнаяматрица, имеющаяобратную,P- матрицаперестановок.

Для этогонайдем матрицу

(18)

По свойству2) матрица

получаетсяиз матрицы

перестановкойвторой и третьейстрок,

Матрица

согласносвойству 3)получаетсяиз

перестановкойвторого и третьегостолбцов

т.е.

-нижняятреугольнаяматрица, имеющаяобратную.

Из (18), учитываяравенство

,получим

(19)

Отсюдаи из (16) видно, что

где обозначено

.ПосколькуР-матрицаперестановоки L-нижняятреугольнаяматрица, свойство(17) доказано. Оноозначает, чтометод Гауссас выбором главногоэлемента постолбцу эквивалентенобычному методуГаусса, примененномук матрице РА,т.е. к системе,полученнойиз исходнойсистемы перестановкойнекоторыхуравнений.

Общийвывод.Результат,полученныйранее для оченьчастного примера,справедливи в случае общейсистемы уравнений(1).

А именно,метод Гауссас выбором главногоэлемента постолбцу можнозаписать в виде

(20)

где

-элементарныематрицы перестановоктакие, что

-элементарныенижние треугольныематрицы.

Отсюда,используясоотношенияперестановочности,аналогичные(19), можно показать,что метод Гауссас выбором главногоэлемента эквивалентенобычному методуГаусса, примененномук системе

PAx=Pf, (21)

где Р -некотораяматрица перестановок.

Теоретическоеобоснованиеметода Гауссас выбором главногоэлемента содержитсяв следующейтеореме.

ТЕОРЕМА1. Если

тосуществуетматрица перестано-

вок Ртакая, что матрицаРАимеет отличныеот нуля угловыеми-

норы.

Доказательствов п.4.

СЛЕДСТВИЕ.Если

тосуществуетматрица престана-

вокР такая,что справедливоразложение

РА=LU, (22)

где L-нижняятреугольнаяматрица с отличнымиот нуля диагональнымиэлементамии U-верхняя треугольнаяматрица с единичнойглавной диагональю.В этом случаедля решениясистемы (1) можноприменять методГаусса с выборомглавного элемента.

4. Доказательствотеоремы 1.Докажем теоремуиндукцией почислу m-порядку матрицыА.

Пустьm=2,т.е.

Если

то утверждениетеоремы выполняетсяпри Р=Е,где Е- единичнаяматрица второгопорядка. Если

,то

,т.к.

Приэтом у матрицы

все угловыеминоры отличныотнуля.

Пустьутверждениетеоремы вернодля любых квадратныхматриц порядкаm-1.Покажем, чтооно верно и.для матрицпорядкаm. Разобьемматрицу Апорядка mнаблоки

где

Достаточнорассмотретьдва случая :

.В первом случаепо предположениюиндукции существуетматрица перестановок

порядкаm-1такая,что

имеетотличные отнуля угловыеминоры. Тогдадля матрицыперестановок

имеем

причем

.Тем самым всеугловые минорыматрицы РАотличныот нуля.

Рассмотримвторой случай,когда

. Т.к.

, найдется хотябы один отличныйот нуля минорпорядка m-1матрицыА,полученныйвычеркиваниемпоследнегостолбца и какой-либостроки. Пусть,например,

где

Переставляяв матрице Астрокис номерами lи m,получимматрицу

,укоторой угловойминор порядкаm-1 имеетвид

и отличаетсяот (23) толькоперестановкойстрок. Следовательно,этот минор неравен нулю имы приходимк рассмотренномувыше случаю.

Теоремадоказана.

ВЫЧИСЛЕНИЕ ОПРЕДЕЛИТЕЛЯМЕТОДОМ ГАУССАС ВЫБОРОМ ГЛАВНОГОЭЛЕМЕНТА.

Одновременнос решениемсистемы линейныхалгебраическихуравнений

можно вычислитьопределительматрицы А.

Пусть в процессеисключениянайдено распожение

т.е.построеныматрицы Lи U. Тогда

и,таким образом,произведениедиагональныхелементовматрицы L(ведущих, главныхелементовметода исключения) равно определителюматрицы РА.Посколькуматрицы РА иА отличаютсятолько перестановкойстрок, определительматрицы РАможет отличатьсяот определителейматрицы А толькознаком.

Аименно,

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

Если матрицаА выроджена,то при использованииметод Гаусса с выбором главногоэлемента постолбцу нанекотором шагеисключенияК все элементыкоторого столбца,находящиесяниже главнойдиагонали ина ней, окажутся равными нулю.Приэтом дальнейшееисключениестановитсяневозможными программадолжна выдатьинформациюо том, что определительматрицы равеннулю.

ОБРАЩЕНИЕ МАТРИЦ.

Нахождение матрицы, обратнойматрице А ,еквивалентнорешению матричногоуравнения

(1)

гдеЕ - единичная матрица, X- искомая квадратнаяматрица.

Уравнение(1) можно записатьв виде системы

уравнений

(2)

где

Можнозаметить, чтосистема (2) распадаетсяна mнезависимых систем уравненийс одной и той же матрицейА , но с различнымиправыми частями.Эти системы имеют

вид( фиксируем j) :

(3)

где

у вектора - столбца

равна единице j-та компонентаи равны нулюостальныекомпоненты.

Например,для матрицывторого порядкасистема (2) распадаетсяна две независимыесистемы:

Длярешениясистем (3) используетсяметод Гаусса( обычный илис выбором главногоэлемента).

Рассмотримприменение метода Гауссабез выбораглавного элемента.Поскольку всесистемы (3) имеютодну и ту жематрицу А ,достаточно один раз совершитьпрямой ходметода Гаусса,т.е. получитьразложение A=LU и запомнитьматрицы L i U .

Обратныйход осуществляетсяпутем решениясистем уравнений

стреугольнымиматрицами L и U.

Приосуществленииобратного ходаможно сократитьчисло действий,принимая вовнимание специальныйвид правыхчастей системы(4).

Запишемподробнеепервые j-1уравненийсистемы (4):

Учитывая невырожденностьматрицы L( т.е.

отсюдаполучаем

Приэтом оставшиесяуравнениясистемы (4) имеютвид

Отсюдапоследовательнонаходятсянеизвестные

по формулам:

Можнопоказать, чтообщее числодействий умноженияи деления, необходимое для обращенияматрицы указаннымспособом, порядка

.Тем самым обращениематрицы требуетне намногобольше времени,чем решениесистемы уравнений.

ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ

АЛГЕБРАЇЧНИХ РІВНЯНЬ.

Розглядаєтьсясистема лінійнихалгебраїчнихрівнянь

(1)

де

- квадратнаматриця вимірності

-вектор - стовпецьправих частинсистеми;

- вектор - стовпецьневідомих.

Ідеянайпростішихітераційнихметодів розв’язаннясистеми (1) полягаєу наступному.За допомогоюеквівалентнихперетво-реньсистема (1) зводитьсядо системивигляду

(2)

де

-квадратнаматріця

-відомийвектор.

Апотім задаєтьсядеяке початковенаближення

(наприклад,у якості

береться вектор

, або деякийрозв’язоксистеми (1), якийодержуєтьсяіншим методомз деякою похибкою).Інші наближенняпослі-довнознаходятьсяза рекурентноюформулою

(3)

докина деякомукроці не будедосягнутазадана точність

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

Виникаєпитання, заяких умов на

послідовність

збігається(у певному розумінні)до точногорозв’язку

Незупиняючисьна подробицях(дивись спецкурс‘Додат-ковірозділи чисельногоаналізу’),дамо деякідостатні умови,за яких

або

Швидкістьзбіжностіоцінюєтьсянерівністю

де

-відстань міжвекторами

та

,що може бутизаданою:

коливиконуєтьсяумова (4);

коли виконуєтьсяумова (5);

коливиконуєтьсяумова (6).

Задаючипотрібну точність

можна з рівності

одержатинеобхіднукількістьітерацій

,щоб досягтизадане

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

ТЕОРЕМА: Нехай система(2) має єдинийрозв’язок.Послідовнінаближення(3) збігаютьсядо розв’язкусистеми (2) задовільногопочатковогонаближення

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

за модулемменше одиниці.

Повернемосьзараз до способівприведення(1) до форми (2). Запишемо(1) у розгорнутійформі

Якщо

для усіх

, то можна (7)зобразити увигляді

Звідсидва найпростішихітераційнихметода.

МетодЯкобі, якийзадаєтьсярекурентнимспіввідношенням:

МетодЗейделя, де вжезнайдені компонентиберуться управій частиніспіввідношенняз (n+1)-гонаближення,а інші- з n-го наближення:

Можна датиматричну формуметодів Якобіі Зейделя.

Нехайматрицю Анаведено увигляді:

де

-нижня трикутнаматриця з нульовоюголовною діагонал-лю;

D- діагональнаматриця з

на головнійдіагоналі;

-верхнятрикутна матрицяз нульовоюголовною діагоналлю.

Заприпущенням

існує

Тодізображеннюу формі (8) відповідає

або

Такимчином, методуЯкобі відповідаєітераційнапроцедура

МетодуЗейделя відповідає

Використовуючисформульованіраніш достатніумови збіжності

, самостійнопереконайтесь,що достатнімиумовами збіжностіметоду Якобіє

або

тобтодіагональнепереваженняматриці А.

Можнадовести, що завказаних умовзбігаєтьсяі метод Зейделя.

Покажемо,що до форми(2), що задовольняєумовам збіжності,може бути зведенадовільна система(1) з

Дійсно,візьмемоматрицю

де

-матрицяз достатньомалими за модулемелементами.Множачи (1) злівана С маємо

тобтоодержали форму(2) з

Зарахунок виборудостатньо малих

можна задовольнитиумовам збіжності.

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

ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ

АЛГЕБРАЇЧНИХ РІВНЯНЬ.

Розглядаєтьсясистема лінійнихалгебраїчнихрівнянь

(1)

де

- квадратнаматриця вимірності

-вектор - стовпецьправих частинсистеми;

-вектор - стовпецьневідомих.

Ідеянайпростішихітераційнихметодів розв’язаннясистеми (1) полягаєу наступному.За допомогоюеквівалентнихперетвореньсистема (1) зводитьсядо системивигляду

(2)

де

-квадратнаматріця

-відомийвектор.

Апотім задаєтьсядеяке початковенаближення

(наприклад,у якості

береться вектор

, або деякийрозв’язоксистеми (1), якийодержуєтьсяіншим методомз деякою похибкою).Інші наближенняпослідовнознаходятьсяза рекурентноюформулою

(3)

докина деякомукроці не будедосягнутазадана точність

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

Виникаєпитання, заяких умов на

послідовність

збігається(у певному розумінні)до точногорозв’язку

Незупиняючисьна подробицях(дивись спецкурс‘Додатковірозділи чисельногоаналізу’),дамо деякідостатні умови,за яких

або

Швидкістьзбіжностіоцінюєтьсянерівністю

де

-відстань міжвекторами

та

,що може бутизаданою:

коливиконуєтьсяумова (4);

коливиконуєтьсяумова (5);

коливиконуєтьсяумова (6).

Задаючипотрібну точність

можна з рівності

одержатинеобхіднукількістьітерацій

,щоб досягтизадане

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

ТЕОРЕМА: Нехай система(2) має єдинийрозв’язок.Послідовнінаближення(3) збігаютьсядо розв’язкусистеми (2) задовільногопочатковогонаближення

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

за модулемменше одиниці.

Повернемосьзараз до способівприведення(1) до форми (2). Запишемо(1) у розгорнутійформі

Якщо

для усіх

,то можна (7) зобразитиу вигляді

Звідсидва найпростішихітераційнихметода.

МетодЯкобі, якийзадаєтьсярекурентнимспіввідношенням:

Можнадати матричнуформу методівЯкобі і Зейделя.

Нехайматрицю Анаведено увигляді:

де

-нижнятрикутна матрицяз нульовоюголовною діагоналлю;

D- діагональнаматриця з

на головнійдіагоналі;

-верхнятрикутна матрицяз нульовоюголовною діагоналлю.

Заприпущенням

існує

Тодізображеннюу формі (8) відповідає

або

Такимчином, методуЯкобі відповідаєітераційнапроцедура

МетодуЗейделя відповідає

Використовуючисформульованіраніш достатніумови збіжності

,самостійнопереконайтесь,що достатнімиумовами збіжностіметоду Якобіє

або

тобтодіагональнепереваженняматриці А.

Можнадовести, що завказаних умовзбігаєтьсяі методЗейделя.

Покажемо,що до форми(2), що задовольняєумовам збіжності,може бути зведенадовільна система(1) з

Дійсно,візьмемоматрицю

де

-матрицяз достатньомалими за модулемелементами.Множачи (1) злівана Смаємо

тобтоодержали форму(2) з

Зарахунок виборудостатньо малих

можна задовольнитиумовам збіжності.

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

МЕТОД ПРОГОНКИ.

Системауравнений дляопределениякоэффициентовсплайна представляетсобой частныйслучай системлинейныхалгебраическихуравнений

стрехдиагональнойматрицей

,т.е. с матрицей,все элементыкоторой,нележащие наглавной и двухпобочных диагоналях,равны нулю

при

та

Вобщем случаесистемы линейныхалгебраическихуравнений с трехдиагональнойматрицей имеютвид

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

Т.е.матрицу Аможно записать

Идеяметода прогонкисостоит в следующем.Решение системы (1) ищется в виде

где

-неизвестныекоэффициенты, которые последовательнонаходятся от

до

(прямая прогонка),а затем последовательновычисляются

(обратная прогонка).

Выведемформулы длявычисления

Из (3) можно получить

Подставляяимеющиесявыражения для

в уравнение(1),приходим при

к уравнению

Последнееуравнение будетвыполнено есликоэффициенты

выбрать такими,чтобы выраженияв квадратныхскобках обращалисьв нуль.

А именно,достаточноположить

Дляотыскания всех

достаточнозадать

Этиначальныезначения находимиз требованияэквивалентностиусловия (3) при

т.е. условия

, первому изуравнений (2).

Такимобразом, получаем

(5)

Нахождениекоэффициентов

по формулам(4), (5) называетсяпрямойпрогонкой. После того,как прогоночныекоэффициенты

найдены,решение системи(1), (2) находитсяпо рекуррентнойформуле (3), начинаяс

Для началасчета по этойформуле требуетсязнать

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

Иравно

Нахождение

по формулам

(6)

называетсяобратнойпрогонкой. Алгоритм решениясистемы (1), (2)определяемый формулами(4)-(6) называетсяметодомпрогонки.

Метод прогонкиможно пременять,если знаменателивыражений (4),(6) не обрщаютсяв нуль.

Покажем, чтодля возможностипримененияметод прогонкидостаточнопотребовать,чтобы коэффициентысистемы (1), (2)удовлетворялиусловиям

(8)

Сначаладокажем поиндукции, чтопри условиях (7), (8) модули прогоночныхкоэффициентов

не превосходятединицы. Согласно(5), (8) имеем

.Предположим,что

для некоторого

и докажем, что

Преждевсего для любыхдвух комплексныхчисел

докажем неравенство

Изнеравенстватреугольникаимеем

Откуда

Вернемсятеперь к доказательству

,если

.Согласно имеемоценку

а,используя (7) ,получаем

т.е.знаменателивыражений (4)не обращаютсяв нуль.

Более того

Следовательно,

Далее,учитывая второе из условий (8)и только чтодоказанноенеравенство

, имеем

т.е. не обращаетсяв нуль и знаменательв выражениидля

К аналогичномувыводу можноприйти и в томслучае, когдаусловия (7), (8) заменяютсяусловиями

Такимобразом привыполненииусловий (7), (8) (также как и условий(9), (10)) система (1), (2)эквивалентна системе (4)-(6). Поэтому эти условиягарантируютсуществованиеи единственностьрешения системы(1), (2) и возможностьнахожденияэтого решенияметодом прогонки.

Крометого, доказанныенеравенства

обеспечиваютустойчивостьсчета по рекуррентнымформулам (6).Последнееозначает, чтопогрешность,внесеннаяна каком-либошаге вычислений,не будет возрастатьпри переходек следующимшагам.

Действительно,пусть в формуле(6) при

вместо

вычислена величина

Тогдана следующемшаге вычислений,т.е. при

вместо

получимвеличину

и погрешность окажется равной

Отсюдаполучаем, что

,т.е.погрешностьне возрастает.

Подсчитаемчисло арифметическихдействий, выполняемыхпри решениизадачи (1), (2) методомпрогонки.

По формулам(4), что реализуемыес помощью шестиарифметическихдействий, вычисленияпроизводятся

раз,по формуле (6)выполняется 5 арифметическихдействий, наконецпо формуле(3), требующейвсего два действия,вычисленияосуществляются

раз.Итак в методепрогонки всегозатрачивается

арифметическихдействий, т.е. число действийрастет линейноотносительночисла неизвестных

Прирешении жепроизвольнойсистемы линейныхалгебраическихуравненийметодом Гаусcачисло действийпропорциональнокубу числанеизвестных.

ВЫЧИСЛЕНИЕСОБСТВЕННЫХЗНАЧЕНИЙ ИСОБСТВЕННЫХВЕКТОРОВ МАТРИЦ.

Большоечисло задачматематикии физики требуетотысканиясобственныхзначений исобственныхвекторов матриц,т.е. отысканиятаких значений+

,для которыхсуществуютнетривиальныерешения однороднойсистемы линейных алгебраическихуравнений

,(1)

иотыскания этихнетривиальныхрешений.

Здесь

-квадратнаяматрица порядкаm,

-неизвестный вектор - столбец.

Изкурса алгебрыизвестно, чтонетривиальноерешение системы(1) существуеттогда и толькотогда, когда

, (2)

где Е- единичнаяматрица. Еслираскрыть определитель

, получаетсяалгебраическоеуравнениестепени m относительно

.Такимобразом задачаотысканиясобственныхзначений сводитсяк проблемераскрытияопределителя

по степеням

и последующемурешению алгебраическогоуравнения m-й степени.

Определитель

называется характеристическим (иливековым) определителем,а уравнение (2) называется характеристическим (иливековым) уравнением.

Различаютполнуюпроблему собственныхзначений,когда необходимоотыскать всесобственныезначения матрицыА исоответствующиесобственныевекторы, и частичнуюпроблему собственныхзначений,когда необходимоотыскать тольконекоторыесобственныезначения, например,максимальноепо модулюсобственноезначение .

Метод Данилевскогоразвертываниевековогоопределителя.

Определение.Квадратнаяматрица Рпорядкаm называется подобной матрице А, если она представленав виде

гдеS -невыродженнаяквадратнаяматрица порядка m.

ТЕОРЕМА. Характеристическийопределительисходной иподобной матрицысовпадают .

Доказательство.

Идея методаДанилевскогосостоит в том,что матрицаА подобнымпреобразованиямприводится,к так называемойнормальнойформе Фробениуса

Характеристическоеуравнение дляматрицы Р имеетпростой вид

т.е.коэффициентыпри степенях

характеристическогополинома непосредственновыражаютсячерез элементыпервой строкиматрицы Р.

Приведениематрицы Ак нормальнойформе ФробениусаР осуществляетсяпоследовательнопострокам,начиная с последенейстроки.

Приведемматрицу А

подобнымпреобразованиек виду

Пусть

Можн проверить,чтотакой вид имеетматрица

,которая равна

где

Слудующийшаг - приведениематрицы

подобнымпреобразованиемк виду

,где и втораяснизу строкаимеет единицув

-омстолбце, а всеостальныеэлементы строкиравны нулю:

Если

томожно проверить,что такой видимеет матрица

где

Таким образом

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

В этомслучае ( будемназыват егорегулярным) нормальнаяформула Фробениусабудет полученаза ( m-1) шагови будет иметьвид

Рассмотримнерегулярныйслучай, когдаматрица, полученнаяв результатеподобныхпреобразованийприведена ужек виду

иэлемент

. Таким образомобычная процедураметода Данилевскогоне подходитиз-за необходимостиделения наноль.

В этой ситуациивозможно дваслучая. В первомслучае к-й

строкелевее элемента

есть элемент

Тогдадомножая матрицу

слева и справана элементарнуюматрицу перестановок

,получаем матрицу

у которойпо сравнениюс матрицей

переставлены l-яи (k-1)-я строка l-йи ( k-1)-й стодбец.В результате на необходимомнам месте оказываетсяненулевойэлемент

, уже преобразованная часть матрицыне меняется,можно применятьобычный шаг метода Данилевскогок матрице

.Она подбна матрице

(и, следовательно,исходной матрицеА ),т.к. елементарнаяматрица перестановоксовпадает сосвоей обратной,т.е.

Рассмотримвторой нерегулярныйслучай, когдав матрице

элемент

и все элементыэтой строки,которые тоженаходятся левееего, тоже равнынулю. В этомслучае характеристическийопределительматрицы

можно представитьв виде

где

- единичныематрицы соответствующейразмерности,а квадратныематрицы

имееют вид:

Обративмвнимание нато, что матрица

уже нормальнуюформу Фробениуса,и поэтому сомножитель

просто развертываетсяв виде многочленас коэффциентами,равными элементампервой строки.

Сомножитель

,есть характеристический определительматрицы

.Для развертыванияможн опятьприменять методДанилевского,приводя матрицу

подобнымипреобразованиямик нормальнойформе Фробениуса.

Предположимтеперь, чтоматрица Аподобнымпреобразованиям

уже приведенак нормальнойформе Фробениуса.Решая характеристическоеуравнение

находимодним из известныхметодов егокорни

которые являютсясобственнымизначениямиматрицы Ри исходной матрицы А.

Теперьстоит задачаотыскать собственныевекторы, соответствующиеэтим собственнымзначениям, т.е.векторы

такие, что

Решимее следующимобразом: найдемсобственныевекторы матрицыР ,а затем поопределенномусоотношениюя пересчитаемсобственныевекторы матрицыА .Это соотношениедает следующая теорема.

ТЕОРЕМА.Пусть

єесть собственноезначение , а

есть соответствующийсобственныйвектор матрицыР ,которая подобнаматрице А,т.е.

Тогда

есть собственныйвектор матрицыА, соответствующийсобственному значению

Доказательство.Тривиальноследует изтого, что

Домножая левую и правуючасть этогоравенства слева на S,

имеем

А это и означает, что

-собственныйвектор матрицыА ,

отвечающийсобственномузначению

Найдемсобственный векторматрицы Р, котораяимеет нормальнуюформу Фробениусаи подобна матрицеА. Записывая

в развернутойформе, имеем

или

В этойсистеме однаиз переменныхможет бытьсделана свободнойи ей может бытьпридано произвольное значение. Вкачестве таковойвозьмем

и положим

Тогда последовательнонаходим

т.е. искомыйсобственныйвектор матрицыРимеет вид

Если процессприведенияматрицы Ак формеР был регулярным,то

В соответствиис теоремойсобственнымвектором матрицыА для собственногозначения

будет вектор

Такимобразом, задача вычислениясобственныхвекторов матрицыА решена.

НАБЛИЖЕННЯФУНКЦІЙ.ЗАДАЧА ІНТЕРПОЛЯЦІЇ.

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

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

Розглянемодекілька задачнаближенняфункцій.

Постановказадачі інтерполяції.Нехай відомізначення деякої функції

різнихточках

які позначимо

Виникаєзадача поновлення( наближеного)функції

удовільній точці

Інодівідомо, що наближенуфункцію доцільношукати у вигляді

девигляд функції

відомий,а параметри

треба визначити.

Колипараметри

визначаютьсяз умови збігу

і наближеноїфункції

у точках

тобто

то такий спосібнаближенняназивається інтерполяцією.Точки

називаютьсявузламиінтерполяції.

Середспособів інтерполяціїнайбільш поширенимє випадок лінійноїінтерполяції.

де

- деякі відоміфункції. Значеннякоефіцієнтів

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

(1)

тобтоз системи n+1лінійнихрівнянь з n+1невідомими

Уокремому випадку,коли

(2)

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

ТЕОРЕМА.Якщо вузлиинтерполяціїрізні, то існуєєдиний інтерполяційниймногочлен n-гоступеню.

Доведення.Дійсно, системарівнянь (1) у цьомувипадку має вигляд

(3)

Їївизначник євизначникомВандермонда

(4)

У тому,що має місцеправа частинарівності (4) , можна переконатисянаступнимчином.

Віднімаючиперший рядокз усіх наступних,маємо

Віднімаючитепер з кожногостовпця попередній,що множитьсяна

одержуємо

де

тежє визначникомВандермонда,порядок якогона одиницюменше порядкупопереднього.

Зробившиз ним те ж, щоз попереднім,одержимо

Продовжуючианалогічнівикладки остаточноодержимо рівність(4).

Бачимо,що при

Тобто система(3) має єдинийрозв’язок.Теорема доведена.

Такимчином, інтерполяційнийполіном можнаодержати шляхомрозв’язаннясистеми лінійнихалгебраїчнихрівнянь (3).

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

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

нерозв’язуючисистему (3).

ТЕОРЕМА.Інтерполяційниймногочлен можебути записанийу формі

(5)

яканазиваєтьсяінтерполяційниммногочленомЛагранжа .

Доведення.Переконаємосьу цьому безпосередньо.

Приn=1маємо

(6)

Бачимо,що вираз (6) ємногочленпершого ступеню,причому підстановкоюпереконуємося, що

Приn=2

тобтомаємо многочлендругого ступенюі

Нарешті, для довільногонатуральногоn

(7)

де

(8)

Функції(8) є многочленамиступеню n.Отже (7) теж є алгебраїчниммногочленомступеню n.Оскільки

при

маємо

Функціії(многочлени) (8) називаютьсялагранжевими коефіцієнтами.

Зауважимо, що оскількиінтерполяційниймногочлен (7)лінійно залежитьвід значеньфункції

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

ПОХИБКА ІНТЕРПОЛЯЦІЇ МНОГОЧЛЕНОМ.

Можназаписати рівність

(9)

де

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

у вузлах інтерполяції,то ніяких корисних висновківвідносно

зробити неможливо.Одержимо деякийвираз похибкиінтерполяціїу припущенні,що

тобто

-функціянеперервнаразом зі своїми

похідними,

-відрізок,

щомістить усівузли інтерполяції

і точку

Введемопозначення

(10)

ТЕОРЕМА.Якщо

,відрізок

містить усівузли інтерполяції,то для

маємо

(11)

(12)

де

деяка невідоматочка.

Доведення.Шукаємо

у наступномувигляді

(13)

де

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

Зафіксуємодовільне

та розглянемонаступну функціювід

(14)

Цяфункція внаслідок(1), (9), (10), (13) дорівнюєнулеві при

та

тобто у всякомувипадку у

точках відрізку

на якому змінюється

Затеоремою Ролля

дорівнює нулевіне менше ніжу

точках інтервалу

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

у якій

Звідси та з(14), враховуючи, що

одержуємо

Отже,

звідки,у відповідностіз (13), (9) має місце(11), (12).

З(12) одержуємооцінку похибкиінтерполяціїу точці

(15)

таоцінку максимальноїпохибки наусьому відрізку

(16)

де

Інтерполяціяз рівновіддаленимивузлами.

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

Нехай

- вузли інтерполяції,

- крок,

- задані значенняфункції

причому

Введемобезрозмірнунезалежнузмінну

Тодівузлу

відповідає

і, окрімтого, виконуютьсяспіввідношення

Прицьому інтерполяційниймногочленЛагранжа, щовідповідаєвипадку

записуєтьсяу вигляді

У загальномувипадку інтерполяційниймногочленЛагранжа

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

де

Оскільки

де

залишковийчлен інтерполяційногомногочленаможе бути поданийу вигляді

Зауважимо,що з означення

виходить ,щозміні змінної
навідрізку

відповідаєзміназмінної

на відрізку

Томуоцінку максимальноїпохибки інтерполяцііна відрізку

можназаписати унаступномувигляді :

де

Величина

не залежитьвід

.Її можна заздалегідьобчислити чиоцінити. Зокрема,

Враховуючи, що

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

,тобто

Зауважимо,що (враховуючи

)при зменшеннікроку

вдвічі правачастина оцінкизменшитьсямінімум у

разів.

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

,у яку замість

підставлене

, вибирають крок

таблиці значеньфункції

на відрізку

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

інтерполяційногомногочлена.Якщо функція

достатньогладка, то підвищення

спочатку, якправило, ведедо підвищенняприпустимого

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

Зауваження.При заданому

вузли інтерполяції

розташованіз кроком

,доцільно вибиратиз сукупностіусіх вузлівзаданої таблиціфункції так,щоб точка

опинилась якможна ближчедо серединивідрізку

. Це пов’язаноз тим , що коливанняфункцій

та

поблизу серединизгаданоговідрізку менше,

ніжу його кінців.

СКІНЧЕННІТА ПОДІЛЕНІРІЗНИЦІ.

Скінченнірізниці.Нехай

де

-ціле,

.Величина

(1)

називається скінченноюрізницею першогопорядкуфункції

у точці

(зкроком

Величина

називаєтьсяскінченноюрізницею другогопорядку функції

у точці

Взагалі,скінченнарізниця n-гопорядкуфункції

у точці

означаєтьсярекурентнимспіввідношенням

(3)

де

Приобчисленняхскінченнірізниці зручнозаписуватиу вигляді таблиці

Розглянемодеякі властивостіскінченнихрізниць.

Лема1.Якщо

,то існує такаточка

, що

. (4)

Доведення.При n=1маємоз формули скінченнихприростів

Лагранжата з (1)

При

маємо. Позначимо

Тодізгідно (2)

ітому за формулоюскінченнихприростівЛагранжа

(5)

Але

Застосовуючище раз формулускінченнихприростівЛагранжа до

маємо

(6)

де

деяка точка. З (5),(6)

виходить

тобтотвердженнялеми при

Для

лема доводитьсяаналогічно.

Висновокз леми 1. Скінченнарізниця

-гопорядку алгебраічногомногочлена

-гоступеню стала,тобто не залежитьвід

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

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

, то величина

яку можна обчислитичерез табличнізначення функції

за допомогою формули (3), дорівнюєзначенню похідної

у деякій точці

,де

Тому, якщо

мале, то число

можна наближеноприйняти завеличину

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

,або, взагалі,маємо у розпорядженнітільки табличнізначення n+1раздиференційовної функції.

Поділенірізниці.Нехайтепер

-довільніточки (вузли)осі

,причому

при

Значення

функції

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

Число

(7)

називаєтьсяподіленою різницею першогопорядку функції

(відповідноточкам

Очевидно

(8)

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

Поділенарізниця

-гопорядку означаєтьсячерез поділені різниці

-гопорядку зарекурентноюформулою

(9)

Приобчисленняхподілені різницізаписують увигляді таблиці

Лема2.Поділена різниця

-гопорядку можебути подана черезвузлові значенняфункції заформулою

тобтоє симетричноюфункцією своїхаргументів.

Доведення.При

твердженнялеми виходитьз рівності (8).

При

згідно з (9) маємо

Длядовільного

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

Згіднолеми 2 значенняподіленоїрізниці незалежить відпорядку нумерації

вузлів, за якимивона будується.Всього маємо

варіантівнумераціївузлів цілимичислами від 0 до

Лема3.Якщо

тобто вузлирозміщуютьсяна осі з сталимкроком

то між поділеноюрізницею

-гопорядку таскінченноюрізницею

-гопорядку існуєнаступнийзв’язок:

. (12)

Доведення.Для

=1рівність (12)виходить з (1), (7). При довільному

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

Звідсий виникає величина

узнаменникуправої частинирівності (12).

Лема4.Нехай

-мінімальнийвідрізок, щомістить вузли

.Тоді існує такаточка

що

. (13)

Доведення.Для вузлів, щорозміщені зсталим кроком,рівність (13)безпосередньовиходить з лем1, 3.

Доведенняу загальномувипадку можназдійснитинаступнимчином. Візьмемоточку

та побудуємоподілену різницю

-гопорядку

Зцього виразуможна одержати

Співставляючиостаннє з ранішодержанимвиразом дляпохибки

,одержуємо

Покладаючитепер

,одержимо (13).

Висновок з леми 4.Поділена різниця

-гопорядку відалгебраічногомногочлена

-гоступеню маєстале значення,що не залежитьвід вузлів

а поділенірізниці щевищих порядківдорівнюютьнулеві.

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

ІнтерполяційниймногочленНьютона .

Нехай

-довільні вузли, що неспівпадаютьі у яких відомізначення функції

Лема1. Алгебраїчниймногочлен

-гоступеню

єінтерполяційним,тобто

(2)

Доведення.Поперш за всезауважимо,щоподілені різниці

є числа (не залежатьвід

), і тому функція(1) дійсно є алгебраїчниймногочлен

-гоступеню.Доведемо(2) при

.Маємо

Очевидно

Тобтопри n=1рівності (2) справедливі.

Доведемо(2) при

.Маємо

При

рівності (2) доведені .

Придовільномунатуральному

рівності (2)доводятьсяза індукцією.

Многочлен(1) називаєтьсяінтерполяційниммногочленомНьютона длянерівних проміжків.

Згідно теоремі єдностівін тотожньоспівпадає зінтерполяційниммногочленомЛагранжа, тобто

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

на

УінтерполяційногомногочленаЛагранжа виднойого явну залежністьвід кожногозначення функції

Це у багатьохвипадках буваєкорисним. Алепри зміні

інтерполяційниймногочленЛагранжа требабудувати заново.У цьому є йогонедолік.

ІнтерполяційниймногочленЛагранжа (1) міститьне значенняфункції

,а її поділенірізниці. Призміні степеню

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

Випадокравновіддаленихвузлів. Нехай

Тоді,враховуючизв’язокподіленоїрізниці ізскінченноюрізницею

івводячи безрозмірнузмінну

інтерполяційниймногочлен (1)можна переписатиу вигляді

ЦеймногочленназиваєтьсяінтерполяційниммногочленомНьютона дляінтерполяціївперед.

Уньому початоквідліку знаходитьсяу крайньомувузлі

,а використаніскінченнірізниці йдутьу таблиці різницьвід

вправо униз.Інтерполяційниймногочлен (3)зручно використовуватина початкутаблиці.

Інтерполяційниймногочлензвулами

,де

,має вигляд

(4)

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

Уньому початоквідліку

розташованийу крайньомуправому вузлі

,а вікористаніскінченнірізниці йдутьу таблиці від

вправо угору.

Інтерполяційниймногочлен(4) зручно використовуватипри інтерполяціїу кінці таблиці.

Якщопри заданому

у таблиці значеньфункції

з кроком

маємодостатню кількістьвузлів з кожногобоку від

,то доцільновузли інтерполяції

вибирати так,щоб точка

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

Найбільшістотньо задатиінтерполяційниймногочлен увигляді (1), деза

береться найближчийдо

вузол, далі за

приймаєтьсянайближчийдо

вузол, що міститьсяз протилежноговід

боку, ніж

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

,що містятьсяяк можливоближче до

.При токомувиборі вузлівдоданки, щослідують одинза одним у виразі(1), як правило,спадають, якщо

мале, а

невелике.

Можливотакож у розглянутомувипадку використовуватиінтерполяційнімногочлени(3), (4), а також інтерполяційниймногочленЛагранжа.

Назакінченнязазначимо, щозалишковийчлен многочлена(3) має той жевигляд, що і увипадку інтерполяційногомногочленаЛагранжа зрівновіддаленимивуздами, тобто

азалишковийчлен інтерполяційногомногочлена(4) може бути поданоу вигляді

де

-похідна від

-деякаточка мінімальноговідрізку, щомістить вузлиінтерполяції

і точку

Згіднолемі, у якійпоказано, що

та при умові,що

мале, а функція

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

МЕТОДГАУССА С ВЫБОРОМГЛАВНОГО ЭЛЕМЕНТА.

Основнаяидея метода.Может оказаться,что система

Ax=f (1)

,то в процессевычисленийне будет происходитьделение нануль.

(2)

Предположим,что

.Тогда на первомшаге будемисключатьпеременное

.Такой приемэквивалентентому, что система(2) переписываетсяв виде

(3)

Применяетсятакже методГаусса с выборомглавного элементапо столбцу.Предположим,что

. Перепишемсистему (2) ввиде

Матрицыперестановок.Ранее былопоказано, чтообычный методГаусса можнозаписать ввиде

где

ОПРЕДЕЛЕНИЕ2.Элементарнойматрицей перестановок

называетсяматрица, полученнаяиз единичнойматрицы перестановкой

к-йи l-йстрок.

Например,элементарнымиматрицамиперестановоктретьего порядкаявляются матрицы

Произведениедвух (а следовательно,и любого числа)элементарныхматриц перестановокявляется матрицейперестановок(не обязательноэлементарной).
Для любойквадратнойматрицы Аматрица

отличаетсяот Аперестановкойк-йиl-йстрок.
Для любойквадратнойматрицы Аматрица

отличаетсяот Аперестановкойк-гои l-гостолбцов.

(4)

Системаимеет вид (1), где

(5)

(6)

Систему(6) можно записатьв виде

(7)

т.е. онаполучаетсяиз системы (4)путем умноженияна матрицу

перестановок

В результатеот системы (7)перейдем кэквивалентнойсистеме

(8)

или вразвернутомвиде

(9)

Из последнихдвух уравненийсистемы (9) надотеперь исключитьпеременное

.Посколькумаксимальнымэлементомпервого столбцаукороченнойсистемы

(10)

(11)

которуюможно записатьв матричномвиде как

. (12)

Такимобразом система(12) получена из(8) применениемэлемен-тарнойматрицы перестановок

В результатеполучим систему

(13)

или

(14)

Заключительныйшаг прямогохода методаГаусса состоитв замене последнегоуравнениясистемы (14) уравнением

что эквивалентноумножению (13)на элементарнуюнижнюю треугольнуюматрицу

виде

(15)

По построениюматрица

(16)

являетсяверхней треугольнойматрицей сединичнойглавной диагональю.

могутприсутствоватьэлементарныематрицы перестановок

Покажемеще, что из (16)следует разложение

PA=LU, (17)

где L-нижняятреугольнаяматрица, имеющаяобратную,P- матрицаперестановок.

Для этогонайдем матрицу

(18)

По свойству2) матрица

получаетсяиз матрицы

перестановкойвторой и третьейстрок,

Матрица

согласносвойству 3)получаетсяиз

перестановкойвторого и третьегостолбцов

т.е.

-нижняятреугольнаяматрица, имеющаяобратную.

Из (18), учитываяравенство

,получим

(19)

Отсюдаи из (16) видно, что

где обозначено

Общийвывод.Результат,полученныйранее для оченьчастного примера,справедливи в случае общейсистемы уравнений(1).

А именно,метод Гауссас выбором главногоэлемента постолбцу можнозаписать в виде

(20)

где

-элементарныематрицы перестановоктакие, что

-элементарныенижние треугольныематрицы.

PAx=Pf, (21)

где Р -некотораяматрица перестановок.

Теоретическоеобоснованиеметода Гауссас выбором главногоэлемента содержитсяв следующейтеореме.

ТЕОРЕМА1. Если

тосуществуетматрица перестано-

вок Ртакая, что матрицаРАимеет отличныеот нуля угловыеми-

норы.

Доказательствов п.4.

СЛЕДСТВИЕ.Если

тосуществуетматрица престана-

вокР такая,что справедливоразложение

РА=LU, (22)

4. Доказательствотеоремы 1.Докажем теоремуиндукцией почислу m-порядку матрицыА.

Пустьm=2,т.е.

Если

то утверждениетеоремы выполняетсяпри Р=Е,где Е- единичнаяматрица второгопорядка. Если

,то

,т.к.

Приэтом у матрицы

все угловыеминоры отличныотнуля.

где

Достаточнорассмотретьдва случая :

.В первом случаепо предположениюиндукции существуетматрица перестановок

порядкаm-1такая,что

имеетотличные отнуля угловыеминоры. Тогдадля матрицыперестановок

имеем

причем

.Тем самым всеугловые минорыматрицы РАотличныот нуля.

Рассмотримвторой случай,когда

. Т.к.

где

Переставляяв матрице Астрокис номерами lи m,получимматрицу

,укоторой угловойминор порядкаm-1 имеетвид

Теоремадоказана.