Вычислительная математика лекции. Конспект лекций. Санкт петербург 2011 2 Оглавление
 Скачать 3.86 Mb.
|
|
1.4.Правила записи приближенных чисел. Значащей цифрой приближенного числа называют все его цифры, начиная с первой ненулевой справа. Примеры: 0.0103; 0.01300; 2.034. Значащая цифра числа называется верной, если абсолютная погрешность не превосходит единицу разряда, соответствующего этой цифре. Пример: a=0.010300. Имеем 5 значащих цифр. Если Δ=2 10 -6 , то 4 из них верные. При Δ=1 10 -6 все 5 значащих цифр будут верными. Пусть a=0.99999, Δ = 10 -5 . То есть точное значение числа равно 1. В этом случае все 5 значащих цифр будут верными. Связь количества N верных значащих цифр с величиной относительной погрешности δ: δ≤(10 N-1 -1) -1 ≈10 1-N Для того, чтобы число содержало N верных значащих цифр достаточно выполнить неравенство δ≤(10 N +1) -1 ≈10 -N 1.5.Корректность и обусловленность задач и алгоритмов. Задача корректна, если выполнены следующие условия: 1.Решение y Y существует при всех x X. 2.Решение единственно. 3.Решение устойчиво к малым вариациям входных данных. Последнее означает непрерывную зависимость погрешности решения от погрешности входных данных. Корректность задачи часто зависит от того, как задача сформулирована. Простейший пример задача решения квадратного 13 уравнения. Если потребовать вычисления всех корней при условиях a, b, c R; x C, то задача окажется корректной В общем случае следует использовать результаты теории решения некорректных задач, которая занимается разработкой так называемых регуляризующих алгоритмов Обусловленность вычислительной задачи – чувствительность её решения к малым погрешностям входных данных. δ(y)≤ν δ δ(x), где ν δ –относительное число обусловленности. Грубая оценка такова, что, если ν δ ≈ 10 N , то N есть число верных значащих цифр, которые могут быть утеряны в решении по сравнению с входными данными. Задача хорошо обусловлена, если заданные погрешности входных данных отвечают приемлемым погрешностям решения. Некорректные задачи принципиально, а плохо обусловленные практически не решаемы. Аналогичным образом вводятся понятия корректности и обусловленности вычислительных алгоритмов. Корректность алгоритма предполагает выполнение следующих условий. 1. Возможность преобразования любого x X в y Y. 2. Результат y устойчив по отношению к погрещностям исходных данных x (малым приращениям "x" соответствуют приращения "y" того же порядка малости). 3. Результат обладает вычислительной устойчивостью. Хорошо обусловленная задача становится практически не решаемой при использовании плохо обусловленного алгоритма. 14 2. Конечные, разделенные разности и сеточные функции. В процессе разработки и при использовании численных методов часто приходится иметь дело с сеточными или таблично заданными функциями, для которых значения аргумента определены в дискретных точках. Для таких функций своеобразным аналогом дифференциального исчисления является аппарат конечных и разделенных разностей. 2. 1. Конечные разности и их свойства. Пусть задана сеточная функция с равноотстоящими узлами: y(x i ) = y i , x i = x 0 +ih, x [a,b], i = 0, 1,…,n, h=(b-a)/n, x 0 = a. Тогда, конечные разности j – ого порядка в узле x i ∆ j y(x i ) (j=0,..,n) определяются рекуррентными соотношениями: ∆ y(x i ) = ∆ y i = y i+1 – y i , i = 0,1,…,n-1; ∆ 2 y(x i ) = ∆ 2 y i = ∆ y i+1 - ∆ y i , i = 0, 1,…,n-2; ……………………………………………….. ∆ j y(x i ) = ∆ j y i = ∆ j-1 y i+1 - ∆ j-1 y i , i = 0, 1,…,n-j; ………………………………………………… ∆ n y(x i ) = ∆ n y i = ∆ n-1 y i+1 - ∆ n-1 y i , i = 0; Для расчета конечных разностей удобно использовать таблицу: i x i y i ∆ y i ∆ 2 y i ∆ 3 y i ∆ 4 y i ……. 0 x 0 y 0 ∆ y 0 ∆ 2 y 0 ∆ 3 y 0 ∆ 4 y 0 1 x 1 y 1 ∆ y 1 ∆ 2 y 1 ∆ 3 y 1 2 x 2 y 2 ∆y 2 ∆ 2 y 2 3 x 3 y 3 ∆ y 3 4 x 4 y 4 ….. …… …… ……. …… ……. …….. …….. 15 Выясним взаимосвязи между конечными разностями и значениями сеточной функции. 1. Рассчитаем y i через конечные разности в нулевом узле, используя очевидные соотношения: y i = y i-1 + ∆y i-1 (*); ∆ k-1 y i = ∆ k y i-1 + ∆ k-1 y i-1 , (**) Из (*) y 1 = y 0 + ∆y 1 При i = 2 из (*) y 2 = y 1 + ∆y 1 . Подставляя ранее рассчитанное y 1 , имеем y 2 = y 0 + ∆y 0 + ∆y 1 Из (**) при i=1, k=2 получаем ∆ y 1 = ∆ 2 y 0 + ∆ y 0 Таким образом, y 2 =y 0 +2 ∆ y 0 + ∆ 2 y 0 Аналогичным образом получим: y 3 =y 0 +3 ∆ y 0 +3 ∆ 2 y 0 + ∆ 3 y 0 Найденные соотношения используются в качестве базы для доказательства по индукции следующего общего результата 0 0 ! ; биномиальные коэффициенты; 0, при i )! i k k k k i i i i k i y C y C C k i k 0 0 0 ; k i k i i C C y y 2. Рассчитаем ∆ i y 0 по известным значениям сеточной функции. ∆ y 0 = y 1 - y 0 ; ∆ 2 y 0 = ∆ (y 1 –y 0 ) = y 2 -y 1 -(y 1 -y 0 )=y 2 -2y 1 +y 0 ; ∆ 3 y 0 = ∆ ( y 2 -2y 1 +y 0 )=y 3 -3y 2 +3y 1 -y 0 Отсюда по индукции 0 0 ( 1) i i i k k i k k y C y 0 ( 1) k k k l l i k i l l y C y 16 Упражнение 1. Разработать блок схему алгоритма расчета конечных разностей. 2. 2.Разделенные разности и их свойства. Задана сеточная функция f i =f(x i ); i=0,1,…,n; x [a,b]. Шаг сетки произволен. Нумерация узлов произвольная, необязательно в порядке возрастания аргумента. Разделенные разности k – ого порядка в узле x i f(x i ,x i+1 ,…x i+k ) (k=1,..,n) определяются рекуррентными соотношениями: 1 1 1 ( ) ( ) ( , ) , i=0, 1; i i i i i i f x f x f x x n x x 1 2 1 1 2 2 ( , ) ( , ) ( , , ) , i=0, 2; i i i i i i i i i f x x f x x f x x x n x x ………………………………………………………… 1 1 1 ( ,..., ) ( ,..., ) ( , ,..., ) , i=0, ; i i k i i k i i i k i k i f x x f x x f x x x n k x x …………………………………………………………………. 1 1 ( ,...., ) ( ,..., ) ( ,..., ) , i=0. i n i n i n n i f x x f x x f x x x x Для расчета разделенных разностей удобно использовать таблицу: 17 i x i f i f(x i ,x i+1 ) f(x i ,x i+1 ,x i+2 ) f(x i ,…,x i+3 ) 0 x 0 f 0 f(x 0 ,x 1 ) f(x 0 ,x 1 ,x 2 ) f(x 0 ,…,x 3 ) 1 x 1 f 1 f(x 1 ,x 2 ) f(x 1 ,x 2 ,x 3 ) 2 x 2 f 2 f(x 2 ,x 3 ) 3 x 3 f 3 ………. ………… ………… ………… ……….. ……….. Справедливы следующие соотношения: 0 0 0 1 1 0 0, ( ) 1. ( ,..., ) ( )...( )( )...( ) ( ) ( ) n i n i i i i i i i n i n i n i i k k k i f x f x x x x x x x x x x f x x x Доказательство 0 1 1 2 1 2 0 1 2 1 2 0 2 2 0 1 2 2 1 ( , ) ( , ) ( ) ( ) ( , , ) , ( , ) + . Таким образом, f x x f x x f x f x f x x x f x x x x x x x x x x 0 1 0 1 2 0 1 0 2 1 0 0 2 1 2 1 2 2 0 2 1 2 0 ( ) ( ) ( , , ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( )( ) f x f x f x x x x x x x x x x x f x f x x x x x x x x x После приведения подобных членов получим 0 1 2 0 1 2 0 1 0 2 1 0 1 2 2 1 2 0 ( ) ( ) ( ) ( , , ) ( )( ) ( )( ) ( )( ) f x f x f x f x x x x x x x x x x x x x x x 0 1 0 1 0 1 1 0 ( ) ( ) ( , ) ; f x f x f x x x x x x 18 Полученные соотношения, рассматриваемые в качестве базы индукции, доказывают справедливость заявленной формулы. 2. Справедливо следующее соотношение 0 0 0 1 0 1 0 1 2 0 1 1 0 1 ( ) ( ) ( ) ( , ) ( )( ) ( , , ) ... ( ) )...( ) ( , ,..., n n n n n n n n n f x f x x x f x x x x x x f x x x x x x x x x f x x x Доказательство. Очевидно f(x 1 )=f(x 0 )+(x 1 -x 0 )f(x 0 ,x 1 ). Произведем расчет f(x 2 ). 2 1 1 2 0 1 2 0 0 1 2 2 1 2 1 2 1 0 1 2 0 2 1 0 1 2 ( ) ( ) ( , ) f x , x x x f x , x , x ; ( ) ( ) ( )f x , x x x ( )f x , x , x ; f x f x f x x x x f x f x x x x x Подставляя найденное ранее значение f(x 1 ), получаем 2 0 2 0 0 1 2 0 2 1 0 1 2 ( ) ( ) ( )f x , x x x ( )f x , x , x ; f x f x x x x x Используя последнее соотношение в качестве базы индукции, имеем 1 0 0 0 ( ) ( ,..., ) , ( ), i=1, , k i i k k k k j k j f x f x x x x x x n что и требовалось доказать. Упражнение 2. Разработать блок схему алгоритма расчета разделенных разностей. Упражнение 3. Используя таблицу рассчитать разделенные разности по заданным узлам в предположении, что порождающая функция 3 2 ( ) 2 3 1. f x x x x 19 i x i f i f(x i ,x i+1 ) f(x i ,x i+1 ,x i+2 ) f(x i ,…,x i+3 ) 0 -1 -7 5 3 2 1 1 3 14 13 2 2 2 17 53 11 3 4 123 31 4 0 -1 …….. ………. ………. Дополнительные свойства разделенных разностей. 1. Разделенная разность f(x i ,…,x i+k ) является симметричной функцией своих аргументов ( т. е. её значение не меняется при любой перестановке аргументов). 2. Связь разделенных и конечных разностей: 0 0 0 0 ( , ,..., ) , i=1, . ! i i y f x x h x ih n h i Приведенное соотношение легко доказывается, если разделенные разности строить на равномерной сетке с шагом h. 3. Связь разделенных разностей и производных образующей функции f(x). Для установления такой связи обратимся к следующему утверждению. Утверждение. Пусть x 0 , x 1 ,…,x n [a,b] – узлы на интервале [a,b], а f(x k ) сеточные функции, причем f(x) [ , ] n a b C . Тогда разделенные разности и производные функции f(x) связаны повторным интегралом вида 1 1 1 ( ) 0 1 1 2 0 1 1 0 0 0 ( , ,..., ) ( ) . n t t n n n n i i i i f x x x dt dt dt f x t x x Доказательство проводится индукцией по параметру n. 20 1 (1) 1 0 1 0 1 1 0 0 1 1 0 0 ( ) ( ) ( ( )) ( , ). f x f x dt f x t x x f x x x x Аналогично для n=2 1 1 (2) 1 2 0 1 1 0 2 2 1 0 0 1 2 0 1 0 1 2 2 0 ( ( ) ( )) ( , ) ( , ) ( , , ). t dt dt f x t x x t x x f x x f x x f x x x x x Подобным образом устанавливается справедливость интегрального соотношения для любого конечного n. Рассмотренное интегральное соотношение есть частный случай формулы 1 1 1 ( ) 1 2 1 1 0 0 0 ( ,..., ) ( ) . k t t k k i i k k i k i j i j j f x x dt dt dt f x t x x Упражнение 4. Проверить справедливость интегрального соотношения для порождающей функции 3 2 ( ) 2 3 1 f x x x x для второй разделенной разности в точке x 1 =1 . Из доказанного утверждения следует, что ( ) 0 1 ( ) ( , ,..., ) , [a,b]. ! n n f f x x x n Справедливость последнего соотношения становится понятной, если n раз воспользоваться теоремой о среднем и записать 1 1 1 1 1 1 ( ) ( ) 0 1 1 2 0 1 1 2 1 0 0 0 0 0 0 ( , ,..., ) ( ) n n t t t t n n n n n i i i n i f x x x dt dt dt f x t x x f dt dt dt 4. Вследствие свойств 2 и 3, для конечной разности получаем ∆ n y 0 =h n f (n) (ξ), ξ [a,b]. 21 3. Интерполирование функций. 3. 1.Постановка задачи. Алгебраическое интерполирование. Интерполирование функций – один из вариантов аппроксимации, иными словами замены исходной функции другой, близкой функцией, удобной для проведения расчетов. Аппроксимируемая функция задается в табличной форме (сеточная функция) 0 { , ( ) } n i i i i x y x y ; x [a,b]. В качестве аппроксимирующей функции часто берут обобщенный полином 1 1 0 0 ( ) ( ) ( ) ... ( ), n n n n n x a x a x a x где 0 { ( )} n i i x заданный набор базисных функций, a i i=0,…,n подлежащие расчету коэффициенты. Интерполирование использует критерий близости в виде ( ) ; i=0, . n i i x y n Для определения n+1 неизвестных a i i=0,n нужно решить систему n+1 линейных алгебраических уравнений с n+1 неизвестными Pa=y, 0 0 0 0 1 0 1 1 1 0 0 ( ) ( ) ( ) ( ) , a= , y= ( ) ( ) n n n n n n n n x x a y x x a y P x x a y Введем векторы φ j =(φ j (x 0 ) , φ j (x 1 ) ,…,φ j (x n )) T , j=0, . n Будем говорить, что система функций линейно независима на узлах 0 { } n i i x , если 0 0 n i j i тогда и только тогда, когда γ i =0, i=0, , n j=0, . n В этом случае решение системы существует и единственно. 22 Интерполирование называется алгебраическим, если ( ) , i=0, . i i x x n Такая система базисных функций линейно независима на несовпадающих узлах. Отсюда в частности следует, что интерполяционный алгебраический полином, построенный на n+1 несовпадающих узлах, имеет степень не выше n. |