Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Погрешность квадратурных формулОдин из возможных способов оценки точности построенных формул состоит в следующем. Рассмотрим интеграл по элементарному отрезку: Выберем на этом отрезке какую-либо «опорную» точку x = z и разложим подынтегральную функцию в ряд по формуле Тейлора относительно этой точки: — остаточный член используемой формулы Тейлора. Вычисляя интеграл от последней суммы, получаем представление в виде: где коэффициенты A, B, … зависят от значения производных в точке z: Заметим далее, что каждая из рассматриваемых квадратурных формул (прямоугольников, трапеций и Симпсона) в пределах элементарного отрезка может быть представлена следующим образом: со своими коэффициентами r, s, q. Заменяя в (3.10) каждое из значений функции f по формуле Тейлора относительно той же точки z, получим представление приближенного значения в виде, аналогичном (3.9): Сравнивая представления (3.9) и (3.11), обнаруживаем, что кроме первых слагаемых в (3.9), (3.11) совпадает еще некоторое количество (p – 1) слагаемых, так что … Несовпадающие слагаемые характеризуют ошибку квадратурной формулы. Оценивая величины этих слагаемых, приходим к оценке для локальной (на интервале ) погрешности где D — числовая константа, а — p-я производная функции f(x). Суммируя локальные погрешности по всем интервалам, получим требуемую оценку погрешности рассматриваемой формулы интегрирования: где по всему отрезку [a, b] (если шаг интегрирования не постоянен, т.e. то ). Степень p в (3.12) принято называть порядком точности квадратурной формулы. Для рассмотренных квадратурных формул полученные таким образом оценки погрешности имеют вид: — для формулы прямоугольников; — для формулы трапеций; — для формулы Симпсона в случае, когда используются узлы с дробным индексом (3.8) и — для (3.8а). Замечание 1. Для формулы трапеций приведенную оценку можно было бы получить, интегрируя по элементарным отрезкам выражение для остаточного члена соответствующего интерполяционного полинома. Замечание 2.Полученные оценки погрешности, как следует из их вывода, зависят от гладкости подынтегральной функции. Например, при наличии 4-х (и выше) производных y формула Симпсона обеспечивает 4-й порядок точности. Если же только трижды непрерывно дифференцируема на [a, b], то точность формулы Симпсона на порядок уменьшается. Если известны оценки для абсолютных величин соответствующих производных, то, используя (3.12), можно a priori (до проведения расчета) определить шаг интегрирования h = const, при котором погрешность вычисленного результата гарантировано не превышает допустимого уровня погрешности e. Для этого, как следует из (3.12), достаточно решить относительно h неравенство Однако типичной является ситуация, когда величины нужных производных не поддаются оценке. Тогда контроль за точностью вычисляемых результатов можно организовать, проводя вычисления на последовательно сгущающейся сетке узлов интегрирования. 14.3 Правило Рунге. Правило Рунге — правило оценки погрешности численных методов. Основная идея состоит в вычислении приближения выбранным методом с шагом h, а затем с шагом h/2, и дальнейшем рассмотрении разностей погрешностей для этих двух вычислений. Интеграл I вычисляется по выбранной формуле (прямоугольников, трапеций, парабол Симпсона) при числе шагов, равном n, а затем при числе шагов, равном 2n. Погрешность вычисления значения интеграла при числе шагов, равном 2n, определяется по формуле Рунге:
для формул прямоугольников и трапеций , а для формулы Симпсона . Таким образом, интеграл вычисляется для последовательных значений числа шагов , где n0 — начальное число шагов. Процесс вычислений заканчивается, когда для очередного значения N будет выполнено условие , где ε — заданная точность.
Прямые и итерационные методы решения систем линейных алгебраических уравнений. Примеры методов. Достаточное условие сходимости одношаговых итерационных методов. Сходимость метода Якоби.
Рассмотрим систему линейных алгебраических уравнений Ax = f, (1) где А — матрица mхm, х=(х1 х2 … хm)Т – искомый вектор, f =(f1 f2 … fm)T – заданный вектор. Предполагается, что определитель матрицы А отличен от нуля, так что решение х существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А. Известно, что систему (1) можно решить, по крайней мере, двумя способами: либо по формулам Крамера, либо методом последовательного исключения неизвестных (методом Гаусса). При больших m первый способ, основанный на вычислении определителей, требует порядка m! арифметических действий, в то время как метод Гаусса только O(m3) действий. Поэтому метод Гаусса в различных вариантах широко используется при решении на ЭВМ. задач линейной алгебры. Методы численного решения системы (1) делятся на две группы: прямые методы и итерационные методы. В прямых (или точных) методах решение х системы (1) находится за конечное число арифметических действий. Примером прямого метода является метод Гаусса. Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы на самом деле не приводят к точному решению системы (1) и называть их точными можно лишь отвлекаясь от погрешностей округления. Сопоставление различных прямых методов проводится обычно по числу арифметических действий (а еще чаще – по асимптотике при больших m числа арифметических действий), необходимых для получения решения. При прочих равных условиях предпочтение отдается методу с меньшим числом действий. Итерационные методы (их называют также методами последовательных приближений) состоят в том, что решение х системы (1) находится как предел при n->∞ последовательных приближений х(n), где n – номер итерации. Как правило, за конечное число итераций этот предел не достигается. Обычно задается некоторое малое число ε>0 (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка ||x(n)-x||<ε (2) Число итераций n=n(ε), которое необходимо провести для получения заданной точности е (т. е. для выполнения оценки (2)), для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных процессов можно сравнивать по необходимому числу итераций n(ε). К прямым методам относятся метод Крамера, метод Гаусса, метод прогонки (для трехдиагональных матриц). Итерационные методы: метод Якоби, метод Гаусса – Зейделя, метод релаксации. Исследование сходимости итерационных методов Рассмотрим систему линейных алгебраических уравнений Ax=f с невырожденной действительной матрицей А и одношаговый стационарный итерационный метод, записанный в каноническом виде где x0 задан. Теорема 1. Пусть А – симметричная положительно определенная матрица, τ>0 и пусть выполнено неравенство В – 0,5τA>0. (4) Тогда итерационный метод (2) сходится. Доказательство. Достаточно показать, что среднеквадратичная норма решения zn, уравнения (3) стремится к нулю при n->∞ и при любой начальной погрешности z0. Покажем сначала, что при условии (4) числовая последовательность Jn=(Azn, zn) является невозрастающей. Из уравнения (3) найдем откуда получим Вследствие симметричности матрицы А имеем Поэтому (5) Отсюда, учитывая условие (4), получаем неравенство Таким образом, числовая последовательность Jn=(Azn, zn) монотонна и ограничена снизу нулем. Следовательно, существует (6) Далее, из положительной определенности матрицы следует существование константы >0 такой, что Отсюда и из (5) получаем неравенство Переходя в этом неравенстве к пределу при и учитывая (6), убеждаемся в том, что существует
где . Наконец, замечая, что А – положительно определенная и, следовательно, обратимая матрица, получим и тем самым Теорема 1 доказана. Метод Якоби имеет следующий канонический вид где D=diag[a11, a22, … amm]. Таким образом в данном случае B=D, τ=1 Следствие 1. Пусть А – симметричная положительно определенная матрица с диагональным преобладанием, т. е. (8) Тогда метод Якоби сходится. Доказательство. Условие сходимости (4) в данном случае имеет вид A<2D. Покажем, что это матричное неравенство следует из неравенств (8). Рассмотрим положительно определенную квадратичную форму и воспользуемся оценками Из условий симметричности и положительной определенности матрицы А имеем aij=aji, aii>0, i,j= 1, 2, ..., m, и поэтому предыдущая оценка приводит к неравенству Перепишем условие (8) в виде
Тогда из неравенства (9) получим
Что и требовалось доказать.
Итерационные методы вариационного типа. Метод минимальных невязок и метод скорейшего спуска.
Рассмотрим итерационные методы вида (2) в которых параметры выбираются из условия минимума погрешности при заданной погрешности . Здесь D – заданная симметричная положительно определенная матрица, . В зависимости от выбора матриц D и B получим различные итерационные методы. Метод минимальных невязок. Рассмотрим систему (1) с симметричной положительно определенной матрицей А. Обозначим через (3) zk = xk - х и невязка rk связаны равенством Azk= rk. Рассмотрим явный итерационный метод (4) и перепишем его в виде (5) Методом минимальных невязок называется итерационный метод (4), в котором параметр выбирается из условия минимума при заданной норме . Получим явное выражение для итерационного параметра . Из (5) получаем и, следовательно, (6) т. е. невязка rk удовлетворяет тому же уравнению, что и погрешность . Возводя обе части уравнения (6) скалярно в квадрат, получим (7) Отсюда видно, что достигает минимума, если (8) Таким образом, в методе минимальных невязок переход от k-й итерации к (k+1)-й осуществляется следующим образом. По найденному значению хк вычисляется вектор невязки и по формуле (8) находится параметр . Затем по формуле (5) досчитывается вектор . Метод минимальных невязок (5), (8) сходится с той же скоростью, что и метод простой итерации с оптимальным параметром . Теорема 1. Пусть А – симметричная положительно определенная матрица. Для погрешности метода минимальных невязок выполняется оценка (9) Где , = (10) Доказательство. Рассмотрим тождество (7). При заданном векторе rk правая часть этого тождества достигает минимума, если выбрать согласно (8). При любом другом значении правая часть тождества (7) может только увеличиться. Поэтому, полагая в (7) где (11) получим неравенство и, следовательно, . (12) Т.к. =р0, поэтому при всех k справедливо неравенство (13) или, что то же самое, неравенство . Получим , или . Следовательно, будет минимальной, если положить (25) При этом для неявного метода скорейшего спуска справедлива оценка (24), где
Численное решение нелинейных уравнений. Методы простой итерации. Примеры методов. Теорема о сходимости метода простой итерации и ее следствия.
Пусть задана функция f(x) действительного переменного. Требуется найти корни уравнения f(x)= 0 (1) или, что то же самое, нули функции f(x). Уже на примере алгебраического многочлена известно, что нули f(x) могут быть как действительными, так и комплексными. Поэтому более точная постановка задачи состоит в нахождении корней уравнения (1), расположенных в заданной области комплексной плоскости. Можно рассматривать также задачу нахождения действительных корней, расположенных на заданном отрезке. Иногда, пренебрегая точностью формулировок, будем говорить, что требуется решить уравнение (1). Задача нахождения корней уравнения (1) обычно решается в два этапа. На первом этапе изучается расположение корней (в общем случае на комплексной плоскости) и проводится их разделение, т. е. выделяются области в комплексной плоскости, содержащие только один корень. Кроме того, изучается вопрос о кратности корней. Тем самым находятся некоторые начальные приближения для корней уравнения (1). На втором этапе, используя заданное начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня. Не существует каких-то общих регулярных приемов решения задачи о расположении корней произвольной функции f(x). Наиболее полно изучен вопрос о расположении корней алгебраических многочленов f(x)=a0 + a1x+a2x2+... + amxm. (2) Например известно, что если для многочлена (2) с действительными коэффициентами выполнены неравенства f(c)>0, f’(с)>,…, f(m)(c)>0, то положительные корни f(х) не превосходят числа с. Численные методы решения нелинейных уравнений являются, как правило, итерационными методами, которые предполагают задание достаточно близких к искомому решению начальных данных. 2. Метод простой итерации. Он состоит в том, что уравнение (1) заменяется эквивалентным уравнением x = s(x) (3) и итерации образуются по правилу xn+1 = s(xn), n = 0,1,..., (4) причем задается начальное приближение х0. Для сходимости большое значение имеет выбор функции s(x). Эту функцию можно задавать различными способами, однако обычно она берется в виде s(x) = x + τ(x)*f(x), (5) причем функция τ(х) не меняет знака на том отрезке, где отыскивается корень. Метод простой итерации сходится при надлежащем выборе начального приближения х0, если |s'(x0) | < 1, где х. – корень уравнения (1). Отметим, что в форме метода простой итерации (4) можно записать, по существу, любой одношаговый итерационный метод. Примеры методов: метод релаксации, метод Ньютона, метод секущих. Сходимость метода простой итерации. Теорема о сходимости. Перепишем уравнение f(x)= 0 (1) в эквивалентном виде x = s(x) (2) и рассмотрим метод простой итерации xn+1 = s(xn), n = 0, 1, ..., x0 задан. (3) Говорят, что итерационный метод сходится, если последовательность {хn} имеет предел при n->∞. В следующей теореме формулируются условия на функцию s(x), гарантирующие существование и единственность решения уравнения (2) и сходимость метода простой итерации к этому решению. Напомним, что функция s(x) называется липшиц-непрерывной с постоянной q на множестве X, если для всех х', х" Х выполняется неравенство |s(x') – s(x")| q|x' – х"|. (4) В дальнейшем в качестве X будем брать отрезок Ur(a)={ Теорема 1. Если s(x) липшиц-непрерывна с постоянной q (0, 1) на отрезке Ur(a), причем |s(a) – a|<(1 – q)r, (6) то уравнение (2) имеет на отрезке Ur(a) единственное решение х, и метод простой итерации (3) сходится к х* при любом начальном приближении x0 (Ur(a)). Для погрешности справедлива оценка |xk – x*| qk|x0 – x*|, k = 0, 1,2,... (7) Доказательство. Сначала докажем по индукции, что xk Ur(a), k = 0,1,… т. е. что метод простой итерации не выводит за пределы того множества, на котором s(x) липшиц-непрерывна с постоянной q (0, 1). Предположим, что xj Ur(a) при некотором j 0, и докажем, что тогда xj+l Ur(a). Из равенства xj+1 – a = s(xj) – a = (s(xj) – s(a)) + (s(a) – a) получим |xj+1 – a| |s(xj) – s(a)| + |s(a) – a| Учитывая условие липшиц-непрерывности, предположение индукции и условие(6),имеем т.е. Оценим теперь разность двух соседних итераций xj+1—xj. Имеем и поскольку все точки хj, j = 1,2,..., находятся на отрезке Ur(a), получаем оценку и,следовательно, . (8) Оценка (8) позволяет доказать фундаментальность последовательности {xk}. Действительно, пусть p – любое натуральное число. Тогда и согласно (8) имеем (9) Поскольку правая часть неравенства (9) стремится к нулю при и не зависит от р, последовательность {xk} является фундаментальной. Следовательно, существует Переходя в (3) к пределу при и учитывая непрерывность функции s(x), получим x*=s(x*), т. е. х* - решение уравнения (2). Предположим, что х*’ какое – то решение уравнения (2), принадлежащее отрезку Ur(a). Тогда и по условию теоремы Так как q<1, последнее неравенство может выполняться лишь при , т.е. решение единственно. Докажем оценку погрешности (7). Из уравнения (3) получим и так как , приходим к неравенству (10) справедливому для всех k = 0, 1, ..., из которого и следует оценка (7). Теорема 1 доказана. Приведем следствия из теоремы 1, содержащие более удобные для проверки условия сходимости. Будем предполагать, что s(x) непрерывно дифференцируема на отрезке Ur(a). Следствие 1. Если (12) для , выполнено условие (6) и , то уравнение (2) имеет единственное решение , метод (3) сходится и справедлива оценка (7). 48. Линейные многошаговые методы для задачи Коши обыкновенных дифференциальных уравнений. Максимальный порядок аппроксимации m-шагового метода. Методы Адамса и Гира. Условие корней.
В одношаговых методах поиск значения зависит только от информации в предыдущем узле xi . Представляется вполне вероятным, что можно добиться большей точности, если использовать информацию о значении функции в нескольких предыдущих узлах, т.е . Так поступают в методах, называемых многошаговыми.
Имеем задачу Коши для обыкновенного дифференциального уравнения первого порядка . (1) (2)
Будем решать задачу (1)-(2) конечноразностными многошаговыми методами. Для этого введем равномерную сетку с постоянным шагом h>0. Введем сеточную функцию и функцию правой части . Линейным m-шаговым разностным методом называется система разностных уравнений (3)
- числовые коэффициенты, не зависящие от номера узла i, параметр j=0,1,2,…,m, причем . Из этого уравнения (3) мы можем выразить значение сеточной функции через ранее найденные значения. Расчет начинается с узла с номером m (i=m), т.е. c уравнения (4) Следовательно, для начала расчетов необходимо знать m значений сеточной функции в узлах . Значение определяется исходной задачей Коши – условием (2), т.е . Значения можно вычислить любым одношаговым методом, например методом Рунге-Кутта нужного порядка точности. Поэтому в дальнейшем можно полагать, что все необходимые значения известны.
Из уравнения (3) видно, что в отличие от методов Рунге-Кутта многошаговые разностные методы допускают вычисления правых частей только в узлах основной сетки . Многошаговые методы можно разделить на явные и неявные.
Метод (3) называется явным, если коэффициент в правой части . (5)
Схема (5) иначе называется экстраполяционной. Искомое значение сеточной функции (6) в этом случае выражается явным образом через m предыдущих значений. Если коэффициент , то метод называется неявным или интерполяционным. Тогда для нахождения значения сеточной функции необходимо решить нелинейное уравнение вида (7) Где Обычно это уравнение (7) решают методом Ньютона, выбирая начальное приближение.
В практике наибольшее распространение получили многошаговые методы Адамса и методы Гира, которые являются частным случаем многошаговых методов. В методах Адамса первая производная искомой функции u(x) задачи Коши аппроксимируется только по двум узлам и (т.е коэффициенты ). В методах Гира первая производная аппроксимируется по m+1 узлу а коэффициенты Т.к коэффициенты в РС определены с точностью до постоянного множителя то для устранения произвола обычно полагается .
Выясним влияние на порядок аппроксимации схемы. Для этого оценим разность левой и правой частей на точном решении u(t). Разлагая в ряд Тейлора u(x) в xi легко получить Тогда погрешность аппроксимации равная разности левой и правой частей схемы будет иметь вид:
Применяем порядок суммирования и после преобразований получаем:
Порядок аппроксимации m-шагового метода неявного <= 2m явного <=2m-1 неявного Адамса <=m+1 явного Адамса <=m Гира <=m
№49. (№19, часть 2). Двухслойная разностная схема для уравнения теплопроводности. Аппроксимация схемы с весами (без вывода). Исследование устойчивости схемы с весами методом гармоник.
Под разностной схемой (РС) понимается совокупность разностных уравнений, аппроксимирующих основное дифференциальное уравнение во всех внутренних узлах сетки и дополнительные (начальные и граничные) условия – в граничных узлах сетки.
Уравнение теплопроводности– дифференциальное уравнение с частными производными параболического типа, описывающее процесс распространения теплоты в сплошной среде; уравнение выражает баланс для малого объема среды с учетом поступления теплоты от источника и тепловых потерь через поверхность элементарного объема вследствие теплопроводности.
Рассмотрим следующую краевую задачу для уравнения теплопроводности с постоянными коэффициентами. Искомая функция зависит от двух переменных и удовлетворяет уравнению в частных производных следующего вида:
для с начальными и граничными условиями. Уравнение (1) известно как уравнение теплопроводности, т.к. описывает температуру тонкой металлической пластины в момент времени в точке с заданным распределением температуры в начальный момент (2) и с нагретыми границами согласно (3).
Введем сетку в области изменения независимых переменных и зададим шаблон(минимальное количество точек, по которому можно построить РС и применить какой-либо метод для вычисления значений) следующего вида: где – пространственно временные сетки. Узлы называются граничными узлами и принадлежат они следующим отрезкам: Остальные точки, не принадлежащие данным отрезкам, называются внутренними узлами. Слоемназывается множество всех узлов сетки , имеющих одну и ту же временную координату. Например, -й слой: - множество узлов на -м слое. Среди двухслойных РС для уравнения теплопроводности различают следующие: 1. Явная РС; 2. Неявная РС; 3. Симметричная РС (схема Кранка-Николсона); 4. РС с весами. Рассмотрим каждую из этих схем более подробно.
Обозначим через приближенное решение задачи (1)-(3) в узлах сетки, т.е.
Явной РСдля уравнения теплопроводности (1)-(3) называется РС, использующая следующий шаблон: и имеющая вид: где - первая разностная производная, а – вторая. Тогда данную РС можно записать следующем виде: После определенных преобразований и введения замены получим, что явная разностная схема для первой краевой задачи для уравнения теплопроводности будет иметь вид: где
Неявной РСдля уравнения теплопроводности (1)-(3) называется РС, использующая следующий шаблон: и имеющая вид: После определенных преобразований и введения замены получим, что неявная разностная схема для уравнения теплопроводности будет иметь вид: где
Симметричной РСдля уравнения теплопроводности (1)-(3) называется РС, использующая следующий шаблон: и имеющая вид: где
|
||
Последнее изменение этой страницы: 2016-08-11 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |