Xreferat.com » Рефераты по математике » Численные методы

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

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

Число

(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) для інтерполяції назад.


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


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

Ax=f (1)

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

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

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

(2)

Предположим, что . Тогда на первом шаге будем исключать переменное . Такой прием эквивалентен тому, что си­стема (2) переписывается в виде

(3)

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

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


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

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

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

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

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

ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок на­зывается матрица, полученная из единичной матрицы перестановкой к-й и l-й строк.

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

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

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

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

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

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

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: