Математические методы в автоматизации и электроснабжении

Пермский национальный исследовательский политехнический университет КОНСПЕКТ ЛЕКЦИЙ по курсу: “Математические методы в автоматизации и электроснабжении”. Составил: к.т.н., доцент Андриевская Н.В. ПЕРМЬ 2012 Список литературы 1. Б.П. Демидович, И.А. Марон. Основы вычислительной математики. М. 1963 г. 2. Н.Н. Калиткин. Численные методы. М. 1978 г. 3. Е.А. Волков. Численные методы. М. 1987 г. 4. Н.В. Копчёнова, И.А. Марои. Вычислительная математика в примерах и задачах. М. 1972 г. Введение. Понятие о численных методах. История развития численных методов. Современное развитие науки и техники тесно связано с использованием ЭВМ, ставшим рабочим инструментом учёного, инженера, конструктора. ЭВМ позволяет строить математические модели сложных устройств и процессов, при этом резко сократить время и стоимость инженерных разработок. Широкое использование ЭВМ способствовало развитию вычислительной математики (прикладной математики). Как и любая наука, математика представляет собой сплав "классической" (теоретической) науки и прикладной науки, в роли последней выступает область вычислительных методов. В основе вычислительной математики лежит решение задач математического моделирования численными методами. Решение задач этими методами даёт приближенное решение, но в ряде случаев это выгодно, так как не всегда представляется возможность разрешить математическую задачу аналитически, а методы решения настолько громоздки и трудоемки, то полученное решение становится приемлемым для проектного применения. Разработанные на сегодняшний момент численные методы перекрыли практически всю классическую математику моделирования. Применение приближенных численных методов во многих случаях более предпочтительно даже тогда, когда известен точный метод решения, так как достаточная точность и небольшие затраты времени при использовании ЭВМ обеспечивают получение ценных результатов, не прибегая к громоздким выкладкам. Главная задача вычислительной математики - фактическое нахождение решение с требуемой точностью, тогда как классическая математика решает в основном задачи существования и свойств решения. Вычислительная математика начала свое развитие достаточно давно и в своем движении прошла три этапа: I. Первый этап начался 3-4 тысячи лет назад. Он был связан с несложными задачами арифметики, алгебры и геометрии. Например, ведение конторских книг, вычисление площадей и объемов, расчетами простейших механизмов. Вычислительные средства- палочки, пальцы, камешки и вершина- счеты. II. Второй период начался с Ньютона. В этот период решались задачи астрономии, геодезии и расчета механических конструкций, сводящиеся либо к обыкновенным дифференциальным уравнениям, либо к алгебраическим системам с большим числом неизвестных. Вычислительные средства- таблицы элементарных функций, арифмометры и логарифмические линейки. III. Третий период начался примерно с 1940 года. Толчком к развитию прикладной математики послужили военные задачи, требующие высокой скорости и решения задач. Появились электронные вычислительные машины. В основу изучения и практического использования численных методов положены следующие основополагающие тезисы: 1. Цель расчетов - это понимание, а не числа; 2. Прежде чем решать задачу, необходимо подумать над практическим применением ее решения; 3. ЭВМ многократно увеличивает некомпетентность вычислителя (инженера). До производства вычислений на ЭВМ необходимо представлять физическую сущность процессов, которые инженер моделирует с помощью программы на ЭВМ. Интерполяция функций. Первый этап работы любого вычисления - числа, приближения, погрешность. Второй этап работы - функция, вычисления функции, её приближения. В краце о интерполяции. Интерполяция в простейшем случае заключается в следующем: Существует какая-то функция, на ней заданы точки (называемые узлами интерполяции), требуется построить (интерполированную) функцию, которая принимала бы в указанных узлах те же значения. Постановка задачи. На отрезке заданы n значений аргумента x и соответствующие им значения функции f(x0)=y0; f(x1)=y1; …; f(xn)=yn. Требуется построить функцию F(x), которая бы принимала в точках x те же значения, что и f(x): F (x0)=y0; F (x1)=y1… F (xn)=yn Для чего? Для того, чтобы: 1. Задача интерполяции. Суметь по полученной функции вычислить значения F(z), где z, zxi при i=0,n 2. Задача экстраполяции. Суметь по полученной функции вычислить F(z), где z. Все существующие интерполяционные формулы содержат в себе конечные разности различных порядков. Введём понятие конечных разностей. Конечные разности различных порядков. Пусть: y =f(x) - заданная функция - фиксированная величина приращения аргумента Тогда - называется первой конечной разностью функции y, или конечной разностью первого порядка. Вторая конечная разность, или конечная разность второго порядка. Третья конечная разность, или конечная разность третьего порядка. Т.о., в общем виде: Конечная разность n-го порядка. Пример: Конечные разности различных порядков удобно располагать в форме таблиц двух видов: горизонтальной и диагональной таблиц разностей x y x0 y0 x1 y1 ... ... ... ... ... Диагональная таблица разностей. x y X0 Y0 X1 Y1 X2 Y2 X3 Y3 Пример: горизонтальная таблица функции y = f(x) = x2 при , x0 = 0 начальное значение, x6=5 конечное значение x y 1 2 1 1 3 2 2 4 5 2 3 9 7 2 4 16 9 5 25 Диагональная таблица x y 1 1 1 2 3 2 4 2 5 3 9 При составлении таблиц возможные ошибки вычисляются и диагональная таблица наглядно показывает нам, как отразится ошибка в значении yn. Следует заметить, что максимальная ошибка – в той же горизонтальной строке, где и табличная величина yn. Пример: исправить ошибку в таблице (неверные цифры взяты в скобки). Ошибка 15 13,260 884 16 14,144 884 17 15,912 884 18 15,028 (-4)0 88(0)4 19 16,79(2)6 (8)0 88(8)4 20 17,680 (-4)0 884 21 18,564 884 22 19,448 884 23 20,332 Как видно из таблицы, ход вторых разностей нарушается при x=19. Ошибка распространяется на 3 строки. Находим среднее арифметическое значение второй разности для средней из 3 точек: =, = Внося исправление в табличное значение y для x=19, получим верное значение функции: n=(yn+ )- =16.792-(-0.004)=16.796. Первая интерполяционная формула Ньютона. Пусть для функции y=f(x) заданы значения yi=f(xi) для равноотстоящих значений независимой переменной xi=x0+i*h (i=0,n) , где h - шаг интерполяции. Требуется подобрать полином Pn(x) степени не выше n, принимающий в точках xi значения Pn(xi)=yi (i=0,n) Ньютон решил поставленную задачу: Pn(x)=y0+qy++y0, где q=. Эта формула называется первой интерполяционной формулой Нью-тона. Каков физический смысл имеет переменная q в первой интерполяционной формулой Ньютона. q=, где k - число шагов, необходимых для достижения точки x , исходя из точки x0. Рассмотрим частные случаи n=1 или n=2: n=1 P1(x)=y0+qy0 – линейное интерполирование n=2 P2(x)=y0+qy0+2y0–параболическое (квадратичное) интерполирование Пример: необходимо построить интерполяционный полином Ньютона для функции y= на отрезке c h=1 X 4 5 6 7 8 Y 0.25 0.2 0.167 0.143 0.125 Горизонтальная таблица разностей. x y y 2y 3y 4y 4 0.25 -0.05 0.017 -0.008 0.005 5 0.2 -0.033 0.009 -0.003 6 0.167 -0.024 0.006 7 0.143 -0.018 8 0.125 Т.о., при наличии 5 точек максимальный порядок существующей конечной разности =4, максимальная степень полинома =4. P4(x)=y0+qy0++y0+ Как пользоваться формулой? Допустим, необходимо определить значение в точке x=4.4 Узловые точки x0=4, h=1,тогда q= Точное значение =0.22727. Вторая интерполяционная формула Ньютона. Первая интерполяционная формула Ньютона практически неудобна для интерполирования значений вблизи конца таблицы. В этом случае обычно применяется вторая интерполяционная формула Ньютона. Pn(x)=yn+qyn-1++y0, Пример: y= sin x x , h=5 Горизонтальная таблица разностей. x y y 2y 3y 4y 5y 30 0.5000 0.0736 -0.0044 -0.0005 0.0002 35 0.5736 0.0692 -0.0049 -0.0005 0.0002 40 0.6428 0.0643 -0.0054 -0.0003 45 0.7071 0.0589 -0.0057 50 0.7660 0.0532 55 0.8192 Пример: Отыщем sin(51 o), xn=51, x=50o, q=0.2 Как первая, так и вторая формула Ньютона может быть использована для экстраполирования функции, т.е. для нахождения значений функции y для значений аргументов x, лежащих вне пределов таблицы. Если xx0, то лучше применять вторую интерполяционную функцию Ньютона. Т.е., 1ИФН используется для интерполирования вперёд и экстраполирования назад. 2 ИФН используется для интерполирования назад и экстраполирования вперёд. Как видно из формул 1 и 2 , при интерполяции используется разности: в 1ИФН ny0 , во 2ИФН kyk+_ . Но существуют формулы, называемые формулы с центральными разностями, к ним относятся: • ИФ Гаусса • ИФ Стерлинга • ИФ Бесселя, которые используют разности, расположенные в горизонтальной строке диагональной таблицы, соответствует начальным значениям xk, yk или в строках близлежащих. Но все эти формулы работают только для постоянного шага. Необходимо отметить следующее: при построении интерполяционных формул Ньютона в качестве начального значения выбирается первый или последний узел интерполирования; для центральных формул начальный узел является средним. При применяют формулу Стирлинга, а при - Бесселя. 1ИФН и 2ИФН применяют тогда, когда интерполирование производится в начале или в конце таблицы и нужных центральных разностей не хватает. Общая характеристика интерполяционных формул с постоянным шагом. Может быть представлена в виде диагональной таблицы разностей: x y y 2y 3y 4y Примечание x-2 y-2 2y-3 4y-4 2-я ИФН y–2 3y-3 x-1 y–1 2y-2 4y-3 y-1 3y-2 x0 y0 2y-1 4y-2 ф. Стерлинга y0 3y-1 ф. Бесселя x1 y1 2y0 4y-1 y1 3y0 x2 y2 2y1 4y0 1-я ИФН Мы рассмотрели интерполяционные формулы для равностоящих узлов интерполирования. Рассмотрим формулы для произвольно заданных узлов интерполирования. Наиболее часто используется формула Лагранжа. Интерполяционная формула Лагранжа. Пусть на отрезке [a;b] даны n+1 различных значений аргумента x: x0, x1,…, xn и известны соответствующие их значению функции y=f(x) : f(x0)=y0, f(x1)=y1, f(xn)=yn. Требуется построить полином степени не выше , имеющий в заданных узлах те же значения, что и функция , т.е. Ln(xi)=yi при i=1,n ; , где Li(n)- коэффициенты Лагранжа. Следует отметить, если узлы равностоящие, то интерполяционный полином Лагранжа совпадает с интерполяционной формулой Ньютона. Примечательно то, что формула Лагранжа зависит лишь от yi, а не от разностей. Частные случаи. n=1 При n=1 имеем 2 точки: (x0;y0) и (x1;y1). прямая, проходящая через эти точки- n=2 (x0;y0), (x1;y1), (x2;y2) Пример: 2 1 1 3 2 2 12 3 5 147 L3(x)=x3+x2-x+2 Для вычисления лагранжевых подмножеств удобно составлять следующую таблицу разности: x-x0 x0-x1 x0-x2 ….. x0-xn x1-x0 x-x1 x1-x2 ….. x1-xn x2-x0 x2-x1 x-x2 ….. x2-x1 ….. ….. ….. ….. ….. xn-x0 xn-x1 xn-x2 ….. x-xn Обозначим произведение элементов i-ой строки через Di , а произведение главной диагонали Пn+1(x). Отсюда следует, что: Пn+1(x)=(x-x0)(x-x1)…(x-xn) при i=1,n Для упрощения вычислений можно использовать инвариантность (при равноотстоящих точках лагранжевых коэффициентов),если x= at+b xj= atj+b при j=0,n то Li(n)(x)= Li(n)(t) Схема Эйткена Чаще всего требуется найти не общее выражение Ln(x) , а значение его при конкретных x , тогда будет удобно пользоваться интерполяционной схемой Эйткена: Последовательно вычисляются многочлены: и т.д. Вычисления по схеме Эйткена удобно расположить в таблице: Xi Yi Xi-X Li-1,i Li-2,i-1,i Li-3,i-2,i-1,i X0 Y0 X0-X L01 L012 L0123 X1 Y1 X1-X L12 L123 L1234 X2 Y2 X2-X L23 L234 X3 Y3 X3-X L34 X4 Y4 X4-X Вычисления по схеме Эйткена обычно ведутся до тех пор, пока последовательные значения L01…n(x) и L01…n(n+1) не совпадут по заданной точности. Т.е. процедура является итерационной, легко реализуется и этим обеспечивает возможность автоматического контроля точности вычислений. Пример: x=27, =0,1 i xi yi xi-x Li-1,i Li-2,i-1,i Li-3,i-2,i-1,i Li-4,i-3,i-2,i-1,i 14 68,7 -13 48,33 49,38 49,31 1 17 64,0 -10 49,71 49,26 2 31 44,0 4 48,90 48,21 3 35 39,1 8 50,46 4 40 32,0 13 Формула Ньютона для неравностоящих узлов Разделённые разности Если в таблицах встречаются неравноотстоящие значения аргумента, т.е. таблицы с переменным шагом, то вводят понятие разделённых разностей. Пусть функция задана таблично, где - значения аргумента - значения функции отношения - разделённая разность первого порядка - разделённая разность второго порядка - разделённая разность -го порядка Разделённые разности удобнее всего рассматривать в таблице - таблице разностей Разделённые разности 1-го 2-го 3-го 4-го Интерполяционная формула Ньютона для неравностоящих значений аргумента Дано - значения аргумента - значения функции Апроксимировать таблично заданную функцию полиномом порядка не выше Пример: 1-го 2-го 3-го 1,450 1,127 1,5 3,140 -0,098 0,795 - 0,012 3,4 4,650 -0,18 -0,159 6,8 4,110 Погрешность формулы Ньютона для неравностоящих узлов где - промежуточное значение между точками и Интерполяция сплайками Даны: , разбитый на разные отрезки с узлами и соответствующие им значения функции Сплайком называется функция, которая вместе с несколькими производными непрерывна на заданном отрезке , и на каждом частичном отрезке в отдельности является некоторым алгебраическим многочленом, причём степени многочлена различны. Степень сплайка - максимальная степень многочлена. Дефект сплайка - разность между степенью сплайка и порядком наивысшей производной на отрезке . На практике широкое применение получили кубические сплайки. Таким образом для интерполяции сплайками, необходимо знать не только значения функции в точках и ; а ещё и их производные - наклон сплайка Как задаётся наклон сплайка? 1. Упрощённый способ 2. Если известны значения => 3. Глобальный Сплайки являются наиболее удобным средством апроксимации функций на небольших промежутках, то есть . При апрксимации функций интерполяционными многочленами можно потребовать очень высокой степени полиномы, тогда как разбиения на участки, содержащих несколько участков, правда при этом в савке двух многочленов первая производная терпит разрыв. Многочлены Чебышева Особенность интерполяции функции многочленами Чебышева заключается в том, что приведённые многочлены минимизируют максимальную погрешность Выбор узлов интерполирования На практике ИФН обрывается на членах, содержащих разности в пределах заданной точности. В этом случае остаточный член да 2инф: - 2ИФН (1) - 1ИФН (2) - Лагранж (3) Анализируя погрешности интерполяционных формул, можно сделать следующий вывод: 1. Остаточные члены зависят от выбора узлов интерполирования: (1) и (2) = (2) 2. В первых двух формулах видоизменить что-либо сложно, ибо само условие означает равноотстоящие узлы. 3. В формуле Лагранжа можно выбирать узлы. При неудачном выборе узлов интерполирования погрешность может быть очень большой. если сконцетрировать около одного из концов, то Рациональный вывод узлов, чтобы полином имел наименьшее максимальное значение по абсолютной величине на отрезке => “наименее отклонился от шрся на . Эта задача решима русским математиком Чебышевым где , => это узлы Полином Чебышева Эти узлы неравноотстоящие, а сгущаются около концов отрезка. Обратное интерполирование для равноотстоящих узлов Задача обратного интерполирования заключается в том, чтобы по функции найти значение аргумента . Предположим, что монотонна и значение содержится между и . Заменяя интерполяционным полиномом Ньютона, имеем: • , где число шагов, необходимых для достижения точки , исходя из точки . За начальное приближение принимаем: Применяя метод итерации, получим: Итерационный процесс, останавливается, когда и тогда => Пример: Задано . Определить с точностью 4 11 6 27 8 50 10 83 Горизонтальная таблица разностей: x y y 2y 3y 4 11 16 7 3 6 27 23 10 8 50 33 10 83  Тогда Обратное интерполирование для неравноотстоящих точек Задача обратного интерполирования для случая неравноотстоящих точек непосредственно может быть решена с помощью интерполяционной формулы Лагранжа Или с помощью интерполяционной формулы Ньютона для неравноотстоящих точек Общие выводы по задаче интерполяции 1. Для равноотстоящих узлов интерполирования лучше всего выбирать интерполяционные формулы Ньютона, при этом: а) если значение в начале таблицы - 1ИФН б) если значение в конце таблицы - 2ИФН 2. Существуют интерполяционные центральные формулы, позволяющие интерполировать в середине таблицы, используя близлежащие разности (Гаус, Стерлинг, Бессель) 3. Для неравноотстоящих узлов интерполирования существуют формулы Лагранжа, Ньютона. 4. Если количество узлов больше и существует возможность определения хотя бы первых производных в узлах, то лучше всего исрользовать интерполяцию сплайками. 5. Если существует возможность выбора узлов, то выбирают по условиям Чебышева, которое позволяет уменьшить погрешность аппроксимации. 6. Используя интерполяционные формулы, можно решать задачу обратного интерполирования. 7. Задача обратного интерполирования может быть использована при решении корней уравнения, а именно: , необходимо найти корни. Составляем таблицу по формуле, а затем задаваясь значением => ищат . Оценка погрешности интерполяционной формулы Лагранжа Если для функции интерполяционный полином Лагранжа принимает в точках заданные значения . Возникает вопрос, насколько близко построенный полином приближается к функции в других точках, то есть как велик остаточный член. - абсолютная погрешность интерполяционной формулы Лагранжа (остаточный член) Пример: с какой точностью можно вычислить с помощью ИФЛ для функции Выбрав узлы интерполирования , , • Решение системы линейных уравнений Общая характеристика методов решения систем линейных уравнений Методы решения систем линейных уравнений в основном делятся на две группы: 1. Точные методы - представляющие собой конечные алгоритмы для вычисления корней системы. 2. Итерационные методы - позволяющие получить корни системы уравнений с заданной точночтью путём бесконечных сходящихся процессов. Введём следующие обозначения: - матрица коэффициентов - столбец свободных членов - столбец неизвестных Решение имеет место, если матрица - неособенная, то есть - решение системы с помощью обратной матрицы Сложность нахождения обратной матрицы для заключается в большом времени нахождения . Это обстоятельство обходится с помощью правила Крамера , где - определитель матрицы - определитель матрицы, полученный из матрицы путём замещения -го столбца на столбец свободных членов . Пример: Прямой метод , По правилу Крамера Метод Гаусса. Схема единственного деления Наиболее распространённым приёмом решения системы линейных уравнений является метод Гаусса или метод последовательного исключения неизвестных. Рассмотрим для простоты систему линейных алгебраических уравнений 4-го порядка: 1. Выбираем ведущий элемент 2. Поделив первое уравнение на , получаем , (2) где , , 3. Исключаем переменную из всех последующих уравнений, начиная со второго, путём вычитания уравнения 2, умноженного на коэффициент, стоящий при в соответствующем уравнении. Получаем , где , , 4. Выбираем ведущий элемент во втором уравнении и так далее. Если , то получим систему , (3) то есть матрица имеет диагональный вид: Из системы 3 отыскиваем следующим образом , (4) Процесс приведения матрицы к треугольному виду 3 называется прямым ходом, а нахождение корней по 4 обратным ходом. Пример: прежний, но методом Гаусса. Приводит к системе уравнений: - прямой ход - обратный ход Существует схема единственного деления, которая используется при дирном счёте, но мы либо рассмотрим её на практике, либо вообще не будем рассматривать. То есть в нашем курсе мы ориентируемся на вычислительную технику и все методы интересуют как алгоритмы. Трудоёмкость метода Гаусса 1. Прямой ход 2. Обратный ход Общее число выполняемых арифметических действий то есть для Предложенный метод Гаусса ориентирован на то, чтобы ведущие элементы не равнялись 0. А если на каком-то шаге возникает ситуация, что ведущий элемент равен 0, то тогда схема “формально” непригодна, хотя заданная система может иметь единственное решение. Тогда применяют разновидность метод Гаусса -схема с выбором главного элемента: Метод Гаусса. Схема с выбором главного элемента 1. Выбираем элемент - наибольший по модулю и неявляющийся свободным членом. 2. Вычисляем коэффициенты , для всех -тая строка называется главной строкой. 3. Из каждой неглавной строки вычитаем главную строку, умноженную на . В результате получим матрицу, у которой в -ом столбце все коэффициенты нулевые. 4. Преобразуем матрицу следующим образом: отбрасываем - (главную) строку и -й столбец. Получим матрицу . 5. Делаем подобные преобразования над матрицей до тех пор, пока не получим одну строку из двух столбцов, которая является главной. 6. Для определения . Объединим все главные строки, начиная с последней. После надлежащего изменения неизвестных получается система с треугольной матрицой. При работе на ЭВМ при вывод главного элемента может оказаться достаточно трудоёмкой задачей. Поэтому практически в качестве главной строки берут первую строку, а в качестве главного элемента - наибольший по модулю элемент этой строки. Пример: 1 -0,6 3 1 -1 2 6 11 I 2 5 1 3 -4 -12 -17 3 -0,4 2 1 -1 1 3 4 -0,2 1 -5 3 -3 3 -1 1 -0,333 1,6 0,8 -0,4 -1,2 0,8 II 2 -0,083 0,4 2,2 -2,6 -3,8 -3,8 3 -4,8 3,6 -3,8 0,6 -4,4 III 1 0,571 2,0 -1,665 -1,0 -0,665 2 2,5 -2,915 -3,75 -4,165 IV 1 0,572 1,141 1,713 V 1 2,0 3 VI 1 3,0 4 VII 1 -1,0 VIII 1 1,0 2 Достоинства метода 1. Если матрица вырождения, то перед исключением неизвестной главный элемент считается равным нулю => 2. С помощью метода Гаусса можно вычислить определитель треугольной матрицы. При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной. В этих случаях для нахождения корней системы лучше пользоваться приближёнными численными методами. Метод итераций Дана система уравнений Можно привести систему к такому виду, чтобы диагональные элементы были отличные от нуля, то есть , тогда разрешая -тое уравнение относительно, получаем , (2) где , , или при , . Тогда систему уравнений 2 можно записать в виде: - итерационная формула. Таким образом, выбрав начальные значения и так далее. Итерации останавливаются, когда , Сходимость метода итераций для решения системы алгебраических уравнений Теорема: Система уравнений имеет единственное решение и сходится при любом начальном значении тогда и только тогда, когда все собственные значения матрицы по модулю меньше 1. Если для системы уравнений выполнено хотя бы одно из условий: 1. , 2. , то процесс итерации сходится, независимо от выбора начального условия. Однако этой теоремой в общем случае очень тяжело воспользоваться, поэтому на практике пользуются другим правилом менее жёстким. Если эти условия выполняются, то в принципе логично выбрать для начальных значений. На практике в качестве начального приближения используют вектор свободных членов. Приведение линейной системы к виду, удобному для итерациию. Теорема сходимости накладывает жёсткие условия к коэффициентам данной линейной системы. Однако, если , то эту систему всегда можно привести к такому виду: , чтобы удовлетворить условиям 1 Первый способ. Дано: Домножим это уравнение на матрицу , где , где Второй способ. Каждое -ое уравнение делится на Тогда , , . Тогда уравнение сходимости имеет вид , , Эти неравенствабудут выполняться, если диагональные элементы будут удовлетворять условиям: , , то есть если модули диагональных коэффициентов для которого уравнения системы больше суммы модулей всех остальных коэффициентов. Достоинства метода итераций 1. Если итерации сходятся быстро, то есть для сходимости требуется менее итераций, то выигрыш во времени по сравнению с методом Гаусса: , - число итераций 2. Погрешности округления в методе итераций сказывается значительно меньше, чем в методе Гаусса. Кроме того, метод итерации является самоисправляющимся, то есть отдельная ошибка запрещается в вычислениях, не отражаясь на конечном результате, то есть ошибочное приближение можно рассматривать как новый начальный вектор. 3. Метод итераций становится особенно выгодным при решении систем, у которых значительное число коэффициентов равно нулю. 4. Метод итераций легко программируется. Метод Зейделя Является модификацией метода итераций. Основная идея заключается в том, что при вычислении -го приближения -го корня используются уже вычисленные приближённые корни . Дано: , Выбираем начальное приближение: На -том шаге, согласно Зейделю строим приближение по следующим формулам: 1. Метод Зейделя даёт полную сходимость по сравнению с методом итерации, но приводящий к громоздким вычислениям. 2. Теорема: Для существования единственного решения системы сходимости метода Зейделя достаточно выполнение хотя бы одного из двух условий: 1) , 2) матрица - симметричная положительно определённая (все её соответственно значения положительны) Численное решение систем нелинейных уравнений Постановка задачи Дана система линейных уравнений (1) Введём обозначения: вектор - вектор аргументов: Аналогично вектор функций Тогда систему 1 можно переписать в виде: Система линейных уравнений в общем виде неразрешима. Поэтому мы будем рассматривать только численные методы решения системы линейных уравнений. Метод Ньютона Для уравнения имеет вид: По анологии метод Ньютона для системы линейных уравнений где - вектор аргументов на -ом шаге итерации - значения вектора функций (системы уравнений ) при - обратная матрица Якоби - матрица, Якоби-матрица, состоящая из частных производных Вполне естественно очевидно, что формулу Ньютона можно применять в том случае, когда Якоби-матрица неособенная, невырождённая, то есть . Пример: Дано: Матрица Якоби Превоначальная оцнка 1) 2) 3) -=-= и так далее Результаты итераций лучше всего сводить в таблицу 3,4 0,097 2,2 0,076 1 3,497 2,276 2 Прекращаем вычисления, когда - заданная точность. Как и в любых численных методах встают следующие задачи: о сходимости метода и о выборе начального значения. Сходимость метода Ньютона Вопросами сходимости метода Ньютона занимались такие учёные, как Виллус, Стёпин, Островский, Канторович и другие. Мы же будем рассматривать сходимость, единственность корня и выбор начального условия по Канторовичу. При рассмотрении этих характеристик метода ипользуются понятия нормы. Поэтому прежде дадим определения : -нормой - называется максимальная сумма модулей элементов по строкам. -нормой - называется максимальная сумма модулей элементов по столбцам. -нормой - нызывается квадратный корень из суммы квадратов модулей элементов матрицы Пример: Для оценки матриц, используемых в методе Ньютона для нелинейных систем, будем использовать -нормы, а именно Теорема о существовании корней и сходимости процесса Ньютона Пусть дана нелинейная система уравнений , где - вектор-функция определена и непрерывна вместе со своими частными производными первого и второго порядков в некоторой области . Положим, что - есть точка, лежащая в вместе со своей замкнутой -окрестностью. При этом выполняются следующие условия: 1) матрица Якоби при имеет обратную функцию 2) 3) 4) постоянные удовлетворяют неравенству Тогда процесс Ньютона при начальном приблежении сходится к решению - есть решение такое, что Для проверки условия даёт оценку расходимости начального и первого приблежения. Быстрота сходимости процесса Ньютона Если выполнимы все четыре условия теоремы 1, то для последовательных приближений , справедливо неравенство: где - искомое решение, а При сходимость метода - сверхбыстрая. Единственность решения Если выполнимы все четыре условия, в области то содержится единственное решение системы Выбор начального условия Если выполнимы все четыре условия и , то процесс сходится к единственному решению в основной области при любом выборе начального условия из области Модифицированный метод Ньютона При использовании метода Ньютона наиболее трудоёмким является процесс вычисления обратной матрицы Якоби. Если матрица невырождённая для некоторого приближения , и достаточно близко к (искомому решению), то можно использовать модифицированный метод Ньютона. Метод итераций Дана система нелинейных уравнений: или (1) Допустим, что систему 1 можно привести к виду: (2) Введём обозначения: , , Можно систему уравнений 2 переписать в виде: Приведённое матричное уравнение и есть формула метода итераций Необходимое и достаточное условие сходимости процесса итерации Пусть функции и непрерывны в области , причём в области выполнимо неравенство: где - некоторая константа. Если последовательные приближения , не выходят из области , то этот процесс сходится к единственному решению системы. Следствие: оценка пиближённо На практике лучше всего рассматривать матрицу с элементами Для сходимости должно выполнятся условие 1) 2) 3) Метод скорейшего спуска (градиентный метод) Дана система линейных уравнений: (1) В матричном виде Считаем, что действительны и непрерывно дифференцируемы в их общей области определения. Рассмотрим функцию (2) Очевидно, что если мы найдём решение системы уравнений 1 , то это решение является и решением системы уравнений 2 и наоборот. Предполагаем, что система 1 имеет лишь одно изолированное решение, представляющего собой точку строго минимум функции . Таким образом задача сводится к нахождению минимум функции в -мерном пространстве. Берём точку - нулевое приближение. Через точку проходит поверхность уровня и . Если близка , то поверхность = будет похожа на элипсоид. Из точки движемся по нормали к поверхности до тех пор, пока эта нормаль не коснётся другой поверхности: И так далее. Так как , то двигаясь таким образом, мы быстро приближаемся к точке с минимальным значением , которая соответствует некоему корню . Градиент функции U - набла или grad - есть вектор приложенный к точке , имеющий направление нормали. Из векторных произведений , (3) Как определить ? Для этого рассматривают скалярную функцию : Уравнение 3 можно преобразовать так, чтобы не было явного выражения градиента. Введем обозначения , тогда итерационная формула градиентного метода будет иметь вид: , где Вычисления производятся до тех пор, пока не станет справедливым следующее неравенство: , где  - заданная точность вычисления. Пример. Дана система нелинейных уравнений: Найти решение системы градиентным методом с точностью =0,01 Определим начальное приближение как: Вектор-функция имеет вид: Якобиан, или матрица частных производных имеет вид: 1 итерация 2 итерация Решение системы нелинейных уравнений представлено в таблице: K x x y y z z 0.000 0,100 0.000 0,200 0.000 0,300 1 0.100 0,030 -0.200 0,250 0.300 0,250 2 0,130 0,095 0,050 0,251 0,050 0,209 3 0,035 0,018 -0,201 0,016 0,259 0,013 4 0,017 0,003 -0,185 0,007 0,246 0,001 5 0,014 -0,178 0,245 Таким образом, решение системы уравнений имеет вид: Сходимость градиентного метода Сходимость метода гарантируется при выборе начального приближения вблизи . В любом случае метод может остановитья в точке относительного метода. Численное решение обыкновенных дифференциальных уравнений Обыкновенные дифференциальные уравнения (ОДУ) встречаются при описании движения системы взаимодействующих материальных носителей (механике, химической кинетике, электрических цепях, сопротивлении материалов и многих других явлениях жизни).Ряд важнейших задач сводится к задачам с обыкновенными дифференциальными уравнениями, а именно теория автоматического управления базируется на ОДУ, а также и другие курсы специальности АЭП Простейшим ОДУ является уравнение 1-го порядка: ОДУ n-го порядка имеет вид: Однако любое уравнение n-го порядка можно свести к системе из n уравнений 1-го порядка: или Таким образом, решение дифференциального уравнения n-го порядка сводится к решению системы дифференциальных уравнений 1-го порядка (количество дифференциальных уравнений в системе = n). Если ввести следующие обозначения: , то систему дифференциальных уравнений можно переписать в векторно-матричном виде: (1) Известно, что система n-го порядка имеет множество решений,, которые в общем случае зависят от постоянных С, общее количество которых -n. Общее решение системы ОДУ может быть записано в виде: ,где Для определения значения этих параметров, т.е. выделения единственного решения необходимо учитывать дополнительные условия. В зависимости от выбора дополнительных условий определены следующие типы задач для обыкновенных дифференциальных уравнений: - задача Коши; - краевая задача; - задача на собственные значения. Задача Коши. Задача Коши, или задача с начальными условиями, имеет следующие дополнительные условия: Краевая задача. Когда дополнительные условия заданы как в точке , так и в точке . Задача на собственные значения. Если функция зависит от параметров : , где . Число дополнительных условий должно быть соответственно. Функции где ; удовлетворяющее всем уравнениям, называются собственными дифференциальными или собственными значениями задачи. Методы решения ОДУ. Обыкновенные дифференциальные уравнения могут быть решены следующими методами: 1. аналитическими; 2. численными; 3. графическими; 4. приближенными. Аналитические методы дают решение в виде аналитического выражения. Графические методы дают приближенное решение в виде графика. Численные методы дают частное решение для определенных в виде таблицы, Численные методы применяются только к корректно поставленным задачам, т.е. к таким, у которых малое изменение начальных значений, приводит к малому изменению интегральных кривых. Пример. Пусть дано следующее ОДУ: . Необходимо решить задачу Коши для . Начальные условия имеют вид: Общее решение имеет вид: при решение . Однако при малом изменении начальных условий: решение в точке : . То есть имеет место плохо обусловленная задача. Численные методы решения обыкновенных дифференциальных уравнений. Метод Эйлера. В основе метода Эйлера (метод ломаных) лежит идея графического построения решения дифференциальных уравнений, однако этот метод дает одновременно и способ нахождения искомой функции в численной (табличной) форме. Пусть дано дифференциальное уравнение: с начальными условиями: . Выбрав достаточно малый шаг h, строится система равноотстоящих точек . В методе Эйлера приближенные значения вычисляются последовательно по формулам: . При этом искомая интегральная кривая , проходящая через точку, заменяется ломанной с вершинами ; каждое звено этой ломаной, называемой ломаной Эйлера, имеет направление, совпадающее с направлением той интегральной кривой уравнения , которая проходит через точку y Пример Пусть дано дифференциальное уравнение: с начальными условиями: . Решение ОДУ имеет вид: 0.0 1.000 0.1 1.100 0.2 1.219 Особенности метода Эйлера. Метод очень прост в реализации, но обладает малой точностью, поскольку погрешность каждого нового шага систематически возрастает. Существует модификации метода, повышающие его точность, - методы Эйлера-Коши – первая и вторая улучшенные формулы. Первая улучшенная формула Эйлера Пусть дано дифференциальное уравнение: с начальными условиями: . Решение в каждой точке определяется по формуле: , где . Геометрически это означает, что отрезок ломанная между точками заменяется на два отрезка . Направление первого отрезка совпадает с направлением интегральной кривой в точке , а направление второго отрезка определяется направлением, интегральной кривой в вспомогательной точке. Пример. Пусть дано дифференциальное уравнение: с начальными условиями: . Решение ОДУ имеет вид: 0.0 1.000 0.1 1.109 0.2 1.239 Вторая улучшенная формула Эйлера Пусть дано дифференциальное уравнение: с начальными условиями: . Решение в каждой точке определяется по формуле: , где Геометрически это означает, что определяется направление интегральной кривой в исходной точке и во вспомогательной точке , а в качестве окончательного направления ломаной берется среднее этих направлений. Пример. Пусть дано дифференциальное уравнение: с начальными условиями: . Решение ОДУ имеет вид: 0.0 1.000 0.1 1.110 0.2 1.241 Метод Рунге-Кутта. Метод Эйлера относится к семейству методов Рунге-Кутта. Метод Рунге-Кутта -го порядка имеет вид: , где при фиксированных значениях некоторых параметров: последовательно вычисляются: Наибольшее применение на практике получил метод Руте-Кутта 4-го порядка: , где Метод Рунге-Кутта имеет ряд важнейших достоинств: 1) высокая точность 2) явная схема вычислений за определенное количество шагов и по определенным формулам. 3) возможен переменный шаг, т.е. можно сменить шаг, где функция быстро меняется. 4) легко оформляется. Пусть дано дифференциальное уравнение: с начальными условиями: . Решение ОДУ имеет вид: 0.0 1.000 0.1 1.110 0.2 1.241 МЕТОДЫ ОБРАБОТКИ ЭКСПЕРИМЕНТАЛЬНЫХ ДАННЫХ. ПОСТАНОВКА ЗАДАЧИ Пусть в результате измерений в процессе опыта получена таблица некоторой зависимости: x x1 x2 … xn F(x) y1 y2 … yn Необходимо найти формулу, выражающую эту зависимость аналитически. Необходимо отметить, что такая постановка задачи соответствует постановке задачи интерполяции. Однако в теории обработки экспериментальных данных методы отличаются от методов интерполяции, ранее рассмотренных. Интерполяционные формулы позволяют построить полиномы, значения которых в узловых точках x1 совпадают со значениями y1. Однако такое совпадение в общем случае не означает совпадение характеров поведения исходной и интерполирующей функции. Требования неукоснительного совпадения значений исходной и интерполирующей функции может оказаться тем более неоправданным, если значения y1 получены в результате измерений и являются сомнительными. Это во-первых. Во-вторых, задача интерполяции известными методами, как правило, решается для небольшого отрезка, и найденная, интерполяционная функция может оказаться непригодной для другого отрезка или даже для большего отрезка. Исходя из вышесказанного, следует уточнить задачу методов обработки экспериментальных данных. По заданным табличным данным необходимо найти функцию заданного вида: y = F (x), которая в точках xi принимает значения как можно более близкие к табличным значениям yi. Практически вид приближающей функции F можно определить следующим образом. Строится точечный график функции, заданной таблично, а затем проводиться плавная кривая, по возможности наилучшим образом отражающая характер расположения точек. По полученной таким образом кривой устанавливается вид приближающей функции (обычно из числа простых по виду аналитических функций). Как правило, перед тем, как решить такую задачу необходимо ответить на четыре вопроса: 1) Какие узлы будут использоваться? 2) Какую аналитическая функция будет использоваться? 3) Какой критерий согласия будет использоваться? 4) Какую точность необходимо достичь? УЗЛОВЫЕ ТОЧКИ В принципе это вопрос статистики, а именно той области, которая называется "планированием эксперимента". На практике узловые точки заданы внешними обстоятельствами или используются равноотстоящие точки. Если же существует возможность выбора точек, то выбор осуществляется по формуле Чебышева, как и в методах интерполяции. КЛАСС ФУНКЦИЙ Выбор вида функции осуществляется исходя из общей задачи, в рамках которой решается задача обработки экспериментальных данных. В качестве функции приближения могут быть использованы следующие элементарные функции: - степенная - показательная - дробно-линейная - логарифмическая - гиперболическая - дробно-рациональная - линейная - квадратный трехчлен КРИТЕРИЙ СОГЛАСИЯ Это самый важный вопрос. Решение этого вопроса дает ответ решения задачи наилучшего приближения. Что означает математически наилучшее приближение? Это означает выбрать критерий согласия, который является функцией невязки узловых точек и значениями аппроксимирующей функции: . Выбор наилучшей функции осуществляется по минимуму этого критерия. Существуют три наиболее широко распространенных критерия согласия: - среднеквадратичный; - минимаксный или Чебышева; - вероятностно-зональный. СРЕДНЕКВАДРАТИЧНЫЙ КРИТЕРИЙ Предполагает минимизацию суммы квадратов ошибки в узловых точках: где yi -значение исходной функции в точке хi (табличное); F(хi) -значение аппроксимирующей функции. Среднеквадратичный критерий позволяет получить сглаживание кривой, то есть позволяет отфильтровать зашумленные данные, не требуя никакой дополнительной информации о шумовых характеристиках помех. МИНИМАКСНЫЙ КРИТЕРИЙ ИЛИ КРИТЕРИЙ ЧЕБЫШЕВА Минимаксный критерий Чебышева определяется как: Если применение среднеквадратичного критерия уменьшает среднеквадратичную ошибку, при этом допуская отдельные большие ошибки, то чебышевское приближение - минимаксное - уменьшает экстремальную наибольшую ошибку. По этому этот критерий используется, когда необходимо при аппроксимации избежать больших ошибок. Минимаксный критерий также не использует дополнительную информацию о шумовых характеристиках помех. ВЕРОЯТНОСТНО-ЗОНАЛЬНЫЙ КРИТЕРИЙ К данным критериям относится целая группа критериев. Данные критерии используют (требуют) дополнительную информацию о шумовых характеристиках объекта: • обобщенный метод наименьших квадратов - ковариационные матрицы шума; - максимальное правдоподобие - распределение вероятностей и т.д. ТОЧНОСТЬ Выбор точности приближения осуществляется исходя из условий задачи и выбранного критерия. На практике наибольшее распространение получил метод наименьших квадратов, использующий среднеквадратический критерий. МЕТОД НАИМЕНЬШИХ КВАДРАТОВ ПОСТАНОВКА ЗАДАЧИ Пусть задана таблица измерений: xi x1 x2 … xn F(x) y1 y2 … yn Тогда задача формулируется следующим образом: для функции F(xi), заданной таблицей, найти функции F определенного вида так, чтобы сумма квадратов: В качестве приближающих функций в зависимости от характера точечного графика функции f рассмотрим следующие функции: - степенная - показательная - дробно-линейная - логарифмическая - гиперболическая - дробно-рациональная - линейная - квадратный трехчлен a, b, m, c – неизвестные параметры. Когда осуществлен выбор приближающей функции, то задача приближения сводится к определению значения этих параметров. Рассмотрим задачу в общем виде. Приближающая функция имеет общий вид: Сумма квадратов: Чтобы найти минимум функции , используем необходимое условие экстремума: т. е. Решив эту систему трех уравнений с тремя неизвестными а, в, с мы и получили конкретный вид функции F(x, a, b, c). Естественно, что F(xi) отличается от yi , но отношения будут минимальны в среднеквадратичном случае. Рассмотрим метод наименьших квадратов для различных функций. ЛИНЕЙНАЯ ФУНКЦИЯ. Разделив каждое уравнение на n, получается: Введем обозначения: Таким образом, получается система линейных уравнений с неизвестными: a и b: Разрешив данную систему уравнений относительно неизвестных параметров а и b, определим искомую функцию Результаты вычислений лучше всего оформить в виде таблицы E Значение E определяет близость аппроксимирующей функции к исходной. E определяется по следующей формуле: Естественно, чем меньше E, тем аппроксимирующая функция ближе к исходной функции. КВАДРАТНЫЙ ТРЕХЧЛЕН. После преобразования получается система линейных уравнений с неизвестными: a, b, c. Разрешив данную систему уравнений относительно неизвестных параметров а, b и с, определим искомую функцию . Результаты вычислений лучше всего оформить в виде таблицы E СТЕПЕННАЯ ФУНКЦИЯ Степенная функция имеет вид: Если прологарифмировать данное уравнение, то можно получить следующее: Введя новые переменные: , получим следующее линейное уравнение: . Определив параметры А и В (см. линейную функцию), можно определить параметры степенной функции: Результаты вычислений лучше всего оформить в виде таблицы E Следует заметить, что данный алгоритм справедлив только для положительных значений x и y. ПОКАЗАТЕЛЬНАЯ ФУНКЦИЯ. Показательная функция имеет вид: Если прологарифмировать данное уравнение, то можно получить следующее: Введя новые переменные: , получаем следующее линейное уравнение: Определив параметры А и В (см. линейную функцию), можно определить параметры степенной функции: Результаты вычислений лучше всего оформить в виде таблицы E Следует заметить, что данный алгоритм справедлив только для положительных значений y. ЛОГАРИФМИЧЕСКАЯ ФУНКЦИЯ. Введя новую переменную: , получаем следующее линейное уравнение: Результаты вычислений лучше всего оформить в виде таблицы E Следует заметить, что данный алгоритм справедлив только для положительных значений u. ДРОБНО-ЛИНЕЙНАЯ ФУНКЦИЯ. Преобразуем следующим образом: Введя новую переменную: , получаем следующее линейное уравнение: Результаты вычислений лучше всего оформить в виде таблицы E Следует заметить, что данный алгоритм справедлив только для y, отличных от нуля. ГИПЕРБОЛА. Введя новую переменную: , получаем следующее линейное уравнение: Результаты вычислений лучше всего оформить в виде таблицы E ДРОБНО-РАЦИОНАЛЬНАЯ. Преобразуем следующим образом: Введя новые переменные: , получаем следующее линейное уравнение: Результаты вычислений лучше всего оформить в виде таблицы E Следует заметить, что данный алгоритм справедлив только для x и y, отличных от нуля.