скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

скачать рефератыКурсовая работа: Численные методы

Курсовая работа: Численные методы

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

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

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) ищется в виде

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

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

Выведем формулы для вычисления Численные методы Из (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)

Величина Численные методы называется первой разностной производной.

Пусть Численные методы задана в трех точках Численные методы Численные методы

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

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

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

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

В точке Численные методы она равна

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

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

Численные методы (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) их остаточные члены имеют противоположные знаки.

В рассмотренном примере Численные методы Поэтому Численные методы

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

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

 

 

 




Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

Обратная связь

Поиск
Обратная связь
Реклама и размещение статей на сайте
© 2010.