Главная / Математика / Численные методы: теория и практика

Численные методы: теория и практика



hello_html_m712fcd74.gif

Рассмотрено на заседании МО естественно-математических дисциплин

«___» ________________ 201__ года

Протокол № _____





Оглавление

Постановка задачи и этапы решения. 11

Пример локализации корней. 11

Метод половинного деления 12

Метод хорд и касательных 12

Метод итераций 13

Сведение исходного уравнения к виду, пригодному для применения метода итераций. 13

Суть и обоснование метода итераций. 13

Условие окончания вычислений в методе итераций. 14

Сравнение различных методов. 14

ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ 14

Постановка задачи интерполирования. 14

Линейная интерполяция. 15

Интерполяция многочленом. 15

Единственность интерполяционного многочлена n-й степени. 15

Построение вспомогательных многочленов Лагранжа. 15

Построение многочлена Лагранжа. 16

Оценка погрешности. 16

Сплайн-интерполяции. 17

ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ ФУНКЦИЙ 17

Общая схема 18

МЕТОД ПРЯМОУГОЛЬНИКОВ. 18

МЕТОД ТРАПЕЦИЙ. 18

МЕТОД СИМПСОНА. 18

Метод двойного счета. 20

ПРИБЛИЖЕННЫЕ РЕШЕНИЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ 20

Метод Пикара. 20

метод разложения неизвестной функции Y(х) в ряд, 21

метод Эйлера. 22

Общая схема численных методов. 22

методы Рунге-Кутта 22

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ 23

Постановка задачи и ее качественный анализ. 23

Нахождение наилучшей линейной приближающей функции. 24

Сведение поиска функций другого вида к поиску линейной функции. 26

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ 26

Постановка задачи и ее качественное исследование. 27

Метод Гаусса 27

Прямой ход. 28

Формулы прямого хода 28

Обратный ход 28

Формулы обратного хода. 28

Ручные вычисления по методу Гаусса. 28

Регуляризация решения 29

Описание метода Гаусса для вырожденных систем. 30

Применения метода Гаусса. 30

Нахождение определителя матрицы. 30

Нахождение обратной матрицы 30

Нахождение ранга матрицы. 31

Определение совместности системы. 31

МЕТОД КВАДРАТНОГО КОРНЯ 31

Условие применимости метода квадратного корня. 31

Матричное описание метода квадратного корня. 31

Нахождение матрицы S («квадратного корня» из А) 32

Нахождение вспомогательного вектора Y. 32

Нахождение вектора решения Х. 33

Пример. 33

Компакт-метод. 34

МЕТОД ПРОСТЫХ ИТЕРАЦИЙ 34

Условия применимости метода простых итераций. 35

Описание метода простых итераций. 35

Условие окончания вычислений. 36

Приведение исходной системы к нужному виду. 36

Случай диагонального преобладания. 36

Случай, когда матрица А близка к единичной. 36

Численные методы решения экстремальных задач 37

Численные методы поиска экстремумов функций одной переменной 38

Метод равномерного поиска. 38

Метод поразрядного приближения 38

Метод деления отрезка пополам (или метод дихотомии). 38

Метод квадратичной интерполяции 39

Метод золотого сечения 39

Численные методы поиска экстремумов функций многих переменных 40

Метод координатного спуска 40

Градиентный метод 40

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 41

Постановка задачи. Графический метод 41

Пример 1 (транспортная задача) 41

Пример 2 (расчет рациона) 42

Пример 3 (распределение ресурсов) 42

Задача линейного программирования в общем виде: 43

Графический метод решения задачи линейного программирования. 43

Двойственная задача 44

СИМПЛЕКС - МЕТОД 44

Описание симплекс-метода. 45

Алгоритм симплекс-метода: 46

Пример. 46

Элементы математической статистики 47

Генеральная совокупность. Выборка. Статистические ряды 47

Графическое изображение вариационных рядов. Эмпирическое распределение 48

Средние величины и показатели вариации 49

Средняя арифметическая и ее свойства 49

Дисперсия и ее свойства. Среднее квадратическое отклонение 50

Коэффициент вариации 50

Структурные средние 51

Законы распределения случайных величин 51

Статистические гипотезы 52

Литература 54







ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

Общий объем - 136 часа, из них:

  • Теоретических занятий - 68 часов;

  • Лабораторно-практических занятий - 68 часов

Распределение часов на изучение факультативного курса по классам следующее:

10 класс – 68 часов

11 класс – 68 часов.

Факультативный курс «Численные методы» предусматривает изучение учащимися основных методов и средств выполнения вычислений на ЭВМ.

В ходе освоения факультативного курса учащиеся должны:

Иметь понятие:

  • О роли и месте математических знаний при решении задач в программе Excel;

  • О решении задач на ЭВМ с заданной точностью;

  • Об определении погрешностей вычислений;

  • О возможностях решения математических задач на ЭВМ для обеспечения потребностей пользователей;

  • О видах погрешностей, основных методах решения нелинейных уравнений и систем уравнений, задаче интерполяции, интегралах, дифференциальных уравнениях:

Уметь:

  • Выбирать метод решения задач;

  • Составлять алгоритмы программ для решения математических задач.

Изучение факультативного курса «Численные методы» способствует развитию математического, логического мышления, что является необходимым для учащихся классов естественно-математического направления. Изучение дисциплины имеет практическую направленность и проводится в тесной связи с другими дисциплинами.

Пререквизиты: изучение факультативного курса основывается на имеющихся знаниях, полученных учащимся по дисциплинам «Математика», «Алгебра и начала анализа», «Информатика».

Постреквизиты: изучение факультативного курса «Численные методы» подготавливает к изучению программирования, к решению математических задач на ЭВМ.

Использование межпредметных связей обеспечивает преемственность в изучении материала, исключает дублирование материала и позволяет рационально распределять время.

Для закрепления теоретических знаний и приобретения необходимых практических навыков и умений проводятся практические и лабораторные работы, перечень которых указан в тематическом плане дисциплины.

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








Тематическое планирование


п/п

Тема

Количество часов

теория

практика

10 класс

1

Теория погрешностей

6

6

2

Решение алгебраических и трансцендентных уравнений

10

10

3

Интерполирование функций

4

4

4

Метод наименьших квадратов

4

4

5

Решение систем линейных уравнений различными способами

10

10

11 класс

6

Численное интегрирование функций

4

4

7

Приближенное решение обыкновенных дифференциальных уравнений

4

4

8

Метод квадратного корня

4

4

9

Метод простых итераций

4

4

10

Линейное программирование

4

4

11

Симплекс-метод решения задач линейного программирования

8

8

12

Транспортная задача. Метод потенциалов

6

6

Итого

68

68

Абсолютная погрешностьмодуль разности между точным и приближенным решением

Абсолютное отклонение - отклонение, равное максимальному значению абсолютной величины разности между аппроксимирующей и исходной функциями на данном отрезке

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

Адекватность математической модели - основное требование, предъявляемое к математической модели рассматриваемого явления, заключающееся в том, что модель должна достаточно точно (в рамках допустимых погрешностей) отражать характерные черты явления

Аппроксимации условиеотклонение исходной функции f(x)заданной своими значениями в узлах сетки на отрезке [a,b] f(xi)=fi, xi[a,b] i=0,1…n от приближающей ее функции (x) является достаточно малой величиной на всем отрезке f(x) - (x) = min для x [a,b]

Аппроксимация один из способов приближения функций; замена функции f(x), заданной своими значениями в нескольких точках отрезка некоторой аппроксимирующей функций (x) с целью восстановления ее значений в остальных точках этого отрезка

Аппроксимирующая функция функция (x) аппроксимирует функцию f(x) на отрезке, если она удовлетворяет условию аппроксимации

Глобальная интерполяция - интерполяция, при которойинтерполирующая функция φ(х) строится сразу для всего рассматриваемого интервала изменения х

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

Гиперболическое уравнение – это волновое уравнение вида

Дополнительные условия - условия для выделения частного решения ОДУ, в качестве дополнительных условий могут задаваться значения искомой функции и ее производных при некоторых значениях независимой переменной.

Задача Коши – нахождение частного решения ОДУ с дополнительными условиями, заданными для одного значения независимой переменной.

Задача краевая – нахождение частного решения ОДУ с дополнительными условиями, заданными в нескольких значениях независимой переменной.

Задача, поставленная корректно - задача, в которой для любых значений исходных данных из некоторого класса ее решение существует, единственно и устойчиво по исходным данным

Задачи смешанные – задачи, для которых заданы и начальные , и краевые дополнительные условия.

Значащие цифры - все цифры данного числа, начиная с первой ненулевой цифры

Интегральная (или непрерывная) аппроксимация - аппроксимация при построении приближения на непрерывном множестве точек

Интерполирование – тип точечной аппроксимации, при котором интерполирующая функция hello_html_77f16f3e.jpg, принимает в заданных точках xi те же значения yi, что и исходная функция f(x)

Интерполирующая функция функция (x) интерполирует функцию f(x)на отрезке, если она удовлетворяет условию интерполяции

Интерполяции условиесовпадение значений исходной функции f(x) заданной своими значениями в узлах сетки на отрезке [a,b] f(xi)=fi, xi[a,b] i=0,1…n и приближающей ее функции (x) в узлах сетки f(xi)= (xi)

Интерполяция один из способов приближения функций; замена функции f(x), заданной своими значениями в нескольких точках отрезка некоторой интерполирующей функций (x) с целью восстановления ее значений в остальных точках этого отрезка

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

Итерацияповторение, один шаг итерационного процесса

Квадратичная (параболическая) интерполяция - интерполяция, при которой в качестве интерполяционной функции на отрезке [xi-1,xi+1] принимается квадратный трехчлен

Квадратурные формулыформулы для приближенного вычисления определенного интеграла, основанные на замене интеграла конечной суммой

Конечно-разностные отношения – формулы для приближенного вычисления значений производных функции f(x), основанные на замене бесконечно малых величин приращения функции и приращения аргумента в определении производной конечными числами.

Краевые условия – дополнительные условия, заданные в нескольких значениях независимой переменной

Корректный численный алгоритм (метод) - численный алгоритм (метод), имеющий единственное численное решение при любых значениях исходных данных, а также в случае устойчивости этого решения относительно погрешностей исходных данных

Кусочная (локальная) интерполяция - интерполяция, при которой интерполирующая функция φ(х) строится отдельно для разных частей рассматриваемого интервала изменения х

Кусочно-линейная (или линейная) интерполяция - простейший и часто используемый вид локальной интерполяции, при котором заданные точки соединяются прямолинейными отрезками, и функция приближается ломаной с вершинами в данных точках

Линейным дифференциальным уравнением - называется уравнение, линейное относительно искомой функции и ее производных.

Метод сплайнов - один из методов численного интегрирования, особенно эффективный при строго ограниченном числе узлов

Начальные условия – дополнительные условия, заданные для одного значения независимой переменной

Неявная разностная схема – разностная схема, в каждое уравнение которой входит более одного (как правило, три) неизвестных значения искомой функции. Получается если, при замене (на следующем слое по времени) используется шаблон

Невязкавектор, разница между вектором – правой частью линейной системы при подставлении в нее точного решения X’ и вектором - правой частью линейной системы при подставлении в него приближенного решения X*, если мы решаем линейную систему AX=F, то вектор невязки =F-AX*

Неустранимые погрешности - погрешности, которые не могут быть уменьшены вычислителем ни до начала решения задачи, ни в процессе ее решения

Норма вектора правило, которое в соответствие вектору ставит число; должно удовлетворять аксиомам нормы: 1) ||X||>0 для любых векторов X 0, ||0|| = 0; 2) || X|| =| | ||X|| для любого числа и любого вектора Х; 3)||X+Y|| ||X||+||Y|| для любых векторов X,Y.

Норма матрицы правило, которое в соответствие матрице ставит число; должно удовлетворять аксиомам нормы: 1) ||A||>0 для любой матрицы А, ||Е|| = 1, где Е – единичная матрица; 2) ||АX|| ||A|| ||X|| для любой матрицы А и любого вектора Х; 3)||А+В|| ||А||+||В|| для любых матриц А, В.

Определенный интеграл от функции f(x) на отрезке hello_html_m4ec7a716.jpg - предел интегральной суммы при таком неограниченном увеличении числа точек разбиения, при котором длина наибольшего из элементарных отрезков стремится к нулю

Относительная погрешность - отношение абсолютной погрешности к точному решению

Общее решение ОДУ – решение ОДУ, зависящее от произвольных постоянных Y=j(x,c1,,c2,...cn), где n-порядок ОДУ

Обыкновенными дифференциальными уравнениями- называются такие уравнения, которые содержат одну или несколько производных от искомой функции y(x).

Параболическая (квадратичная) интерполяция - интерполяция, при которой в качестве интерполяционной функции на отрезке [xi-1, xi+1] принимается квадратный трехчлен

Погрешность – это разница между точным и приближенным решением.

Погрешность аппроксимации производной - величина, характеризующая отклонение приближенного значения производной от ее истинного значения

Погрешность ограничения функции, полученной с помощью ряда – погрешность, возникающая из-за учета лишь ограниченного числа членов ряда

Погрешность округлений - погрешность, связанная с ограниченностью разрядной сетки компьютера

Порядок дифференциального уравнения – это наивысший порядок n, входящей в уравнение производной

Порядок точности - показатель степени, с которым шаг входит в оценку погрешности

Приближенное решение – значение, отличающееся от точного решения на некоторую небольшую величину

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

Производная функции у = f(x) - предел отношения приращения функции Δу к приращению аргумента Δх при стремлении Δх к нулю

Прямой метод метод, позволяющий получить решение за конечное число шагов

Разностная схема – дискретный аналог дифференциального уравнения, получается при замене входящие в уравнение частные производные.

Разностная схема устойчивая , если ее решение непрерывно зависит от входных данных, т.е. малым измельчениям входных данных соответствуют малые изменения в решении

Сетка на отрезке [a,b]любое конечное множество точек этого отрезка xi[a,b], i=0,1…n

Сеточная функцияфункция, заданная своими значениями в узлах сетки

Сплайн-интерполяция - один из способов приближения функций; замена функции f(x), заданной своими значениями в узлах сетки на отрезке [a,b] f(xi)=fi, xi[a,b] i=0,1…n сплайном - функцией s(x), удовлетворяющей следующим условиям: 1) на каждом частичном отрезке [xi-1;xi] i=1,2…n функция s(x) является многочленом (для кубического сплайна – многочленом 3 степени); 2) функция s(x), а также ее первая и вторая производные непрерывны на [a,b]; 3) функция s(x) удовлетворяет условию интерполяции.

Сплайн-функция - специальным образом построенный многочлен третьей степени

Сходимостьметод называется сходящимся, если последовательность приближенных решений сходится к точному решению

Сходимость численного метода – стремление значений решения дискретной модели задачи к соответствующим значениям решения исходной задачи при стремлении к нулю параметра дискретизации

Скорость сходимости- показатель степени, с которым шаг входит в оценку погрешности.

Слой – значения искомой функции в фиксированный момент времени.

Точечная аппроксимация - аппроксимация, при которой приближение строится на заданном дискретном множестве точек {xi}

Точное решение – значение, которое превращает решаемое уравнение в тождество

Узел сеткизначение точки сетки

Условие наличия единственного корня на отрезке если непрерывная на отрезке [a,b] функция f(x) меняет знак f(a)f(b)<0, значит на этом отрезке уравнение f(x)=0 имеет корень, если к тому же f(x) монотонна на [a,b], то корень единственный

Устойчивостьметод называется устойчивым, если малые погрешности исходных данных не приводят к большим погрешностям результатов и неустойчивым в обратом случае.

Уравнение с частными производными – дифференциальное уравнение, решением которого является функция многих переменных; содержит частные производные искомой функции.

Устойчивая задача (по исходному параметру х) - задача, в которой малое приращение исходной величины Δх приводит к малому приращению искомой величины Δу

Функция нечетная относительно точки х0 - функция для которой f(-x0) = -f(x0)

Функция четная относительно точки х0 - функция для которой f(-x0) = f(x0)

Число обусловленности матрицыпроизведение нормы матрицы, обратной к данной на норму матрицы: МА=||A-1|| ||A||; характеризует устойчивость численных методов решения линейной системы AX=F

Численные методы - это основной класс методов, с помощью которых решаются прикладные задачи, моделируемые уравнениями с частными производными

Частное решение ОДУ – одно из общего решения ОДУ, в котором производным постоянным даны определенные значения.

Шаг сеткиразность между значениями двух соседних узлов сетки h=xi-xi-1

Экстраполяция - интерполирование, применяемое для приближенного вычисления функции вне рассматриваемого отрезка (х<х0, х>хп)

Явная разностная схема – разностная схема в каждое уравнение которой входит одно неизвестное ( на следующем слое по времени) значение искомой функции. Если при замене производной в дифференциальном уравнении их конечно- разностной аппроксимации используется шаблон

РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ И ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ

Постановка задачи и этапы решения.

При решении алгебраических и трансцендентных уравнений, встречающихся на практике, очень редко удается найти точное решение. Поэтому приходится применять различные приближенные способы определения корней. В общей постановке задачи обычно требуют непрерывность функции f(x), корни которой ищутся с заданной точностью. Решение при этом разбивается на два этапа:

1.ЛОКАЛИЗАЦИЯ корней, т.е. выделение непересекающихся отрезков, каждый из которых содержит по одному корню.

2.УТОЧНЕНИЕ корней, т.е. вычисление корня на каждом из отрезков с нужной точностью.

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

Пример локализации корней.

Приведем лишь один ПРИМЕР: определить количество и приближенное расположение корней уравнения sinX - 0.2X=0.

Для решения перепишем уравнение в виде sinX=0.2X. Поскольку значения функции y=sinX лежат между -1 и 1, то корни уравнения могут быть только на отрезке [-5,5]. Ясно, что один из корней - это X=0 . Если же на отрезке [-5,5] нарисовать графики функций y1(X)= sinX и y2(X)=0.2X, то сразу будет видно, что точки их пересечения (а это и есть корни нашего уравнения) расположены на отрезках [-3,-2] и [2,3].

Ответ: исходное уравнение имеет 3 корня: Х1=0, Х2[-3,-2] и Х3[2,3].

Упражнения: определить количество и месторасположение корней уравнений:

1.1 9 – Х2 - eх = 0

1.2 sin 2X – X2+6=0

1.3 1/(1+X2) - 0.1 X4 = 0

1.4 ln(2+X) - 0.4X3= 0

В дальнейшем мы будем считать, что уравнение f(X)=0 задано на отрезке [a,b], на котором расположен ровно один его корень, и исследовать решение второй части задачи - уточнение корней. По-видимому, эта задача является самой простой из всех вычислительных задач, встречающихся на практике. Существуют несколько хороших методов решения данной задачи.

Метод половинного деления

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

Алгоритм данного метода можно записать так:

1.Ввести данные (a, b, ).

2.Если нужная точность достигнута (| b - a | < 2) то иди к п.6

3.Возьми середину очередного отрезка ( С = ( a + b )/ 2 ).

4.Если значения функции в точках а и С одного знака (f(a)*f(C)>0), то в качестве следующего отрезка возьми правую половину (а=С), иначе левую (b=C).

5.Иди к п.2.

6.Напечатать ответ (( a + b ) / 2 )

Упражнение 1.5 Перевести данный алгоритм на один из языков программирования.

Метод хорд и касательных

(или метод Ньютона, хотя принято называть методом Ньютона не комбинированный метод, а метод хорд) применяется только в том случае, когда . f'(X) и f''(X) не изменяют знака на отрезке [a,b], т.е.функция f(X) на отрезке [a,b] монотонна и не имеет точек перегиба.

Суть метода та же самая - построение последовательности вложенных отрезков, содержащих корень, однако отрезки строятся по-другому. На каждом шаге через концы дуги графика функции f(X) на очередном отрезке проводят хорду и из одного конца проводят касательную. Точки пересечения этих прямых с осью ОХ и образуют следующий отрезок. Процесс построения прекращают при выполнении того же условия (| b - a | < 2).

Для того, чтобы отрезки получались вложенными, нужно проводить ту касательную из конца, которая пересекает ось ОХ на отрезке [a,b]. Перебрав четыре возможных случая, легко увидеть, что касательную следует проводить из того конца, где знак функции совпадает со знаком второй производной. Также несложно заметить, что касательная проводится либо все время из правого, либо все время из левого конца. Будем считать для определенности , что этот конец - b .

Вопрос 1. Почему при описанном выше построении очередной полученный отрезок также содержит корень исходного уравнения? Обоснуйте этот факт геометрически, а если сможете, то докажите его строго.

Формулы, употребляемые в методе Ньютона, хорошо известны из аналитической геометрии:

Уравнение хорды, проходящей через точки (a,f(a)) и (b,f(b)): y = f(a)+(x-a)*(f(b)-f(a))/(b-a),

откуда точка пересечения с осью ОХ: Х= a - f(a) *(b-a)/(f(b)-f(a)).

Уравнение касательной, проходящей через точку (b,f(b)): -y=f(b)+f'(b)(x-b),

откуда точка пересечения с осью ОХ: Х= b - f(b)/f'(b).

При составлении алгоритма снова естественно использовать для концов отрезка только две переменные a и b и писать: a= a - f(a) *(b-a)/(f(b)-f(a)) и (1.1)

b= b - f(b)/f'(b) (1.2)

Однако, в этом случае важен порядок формул (1.1) и (1.2).

Вопрос 2:В каком порядке следует писать формулы (1) и (2) при составлении алгоритма метода Ньютона и почему?

Упражнение 1.6.Составить алгоритм и программу на одном из языков для решения уравнений методом Ньютона.

Метод итераций

применяется к уравнению вида Х= u(x) на отрезке [a,b], где:

а) модуль производной функции u(x) невелик: | u'(x) | <= q < 1 (x[a,b] )

б) значения u(x) лежат на [a,b] ,т.е. a <= u(x) <= b при x[a,b].

Если заранее известно, что на отрезке [a,b] расположен ровно один корень уравнения Х=u(x), то достаточно проверить выполнение условия а).

Упражнения: определить, применим ли метод итераций для уравнений:

1.7 Х=ln(3X+2) на отрезке [0,5]. А на отрезке [1,5]?

    1. Х=е х-9 на отрезке [10,12]. А на отрезке [0,1]?

Сведение исходного уравнения к виду, пригодному для применения метода итераций.

Сведение уравнения f(x)=0 к нужному виду обычно осуществляют одним из двух способов:

  1. Выражают один из Х, входящих в уравнение, например уравнение ех - х-=0 приводят к виду:

Х=ех или Х = ln(х)

2) Подбирают множитель и производят преобразования: f(х)=0 => k*f(x)=0 => х=х + k*f(x), т.е. u(x)=х+ k*f(x). Например, если 0 < m < f'(x) <= M при Х[a,b], то можно в качестве k взять величину - 1/М, и тогда 0 <= u'(x) = 1 +к* f'(x)= 1- 1/M * f' (x) <= 1- m/M

Упражнения. Свести к виду, пригодному для применения метода итераций уравнения:

1.9 х3- 3 х2 + 1 =0 на отрезке [ 2,3 ] .

1.10 x * tg(x/2)- sin(x/2) =0 на отрезке [-1,1 ] .

1.11 9-x2-ex= 0 на отрезке [1,2].

Суть и обоснование метода итераций.

Суть метода итераций заключается в построении рекуррентной последовательности чисел, сходящейся к решению, по формуле хк+1 = u(xк), к=0,1,2,..., где х0[a,b] -произвольная точка.

Справедливость метода обосновывает следующая ТЕОРЕМА:

Пусть на [a,b] задана функция u(x), удовлетворяющая условиям а) и б), а х0 - произвольная точка отрезка [a,b], причем уравнение x=u(x) имеет корень. Тогда последовательность {Xк}, построенная по формуле хк+1 = u(xк) сходится к решению не медленнее, чем геометрическая прогрессия со знаменателем q.

Доказательство: Сравним расстояния от точек хк+1 и xк до решения (обозначим его С), используя теорему Лагранжа:

| хк+1-С| = |u(xк)- u(C)| = | (хк-с) u'(у)|<= |(хк-с)|* max | u'(x) | = q |(хк-с)|,

что и требовалось доказать.

Замечание 1. Требование существования корня приведено в теореме лишь для простоты доказательства.

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

Условие окончания вычислений в методе итераций.

Замечание 3. Процесс построения последовательности следует обрывать, когда станет верным неравенство |хк+1к|< *(1-q)/q. В этом случае хк+1 и дает приближение к решению с требуемой точностью.

Упражнение 1.12. Доказать, что в условиях теоремы из неравенства |хк+1к|< *(1-q)/q вытекает неравенство |хк+1-с|< .

Упражнение 1.13.Составить алгоритм и программу на одном из языков для решения уравнений методом итераций.

Сравнение различных методов.

Сравнение методов обычно производится по следующим критериям:

1.Универсальность.

2.Простота организации вычислений и контроля за точностью.

3.Скорость сходимости.

Если сравнить три приведенных выше метода, то следует отметить, что

1) Самым универсальным является метод половинного деления, поскольку он применим для любой непрерывной функции. Однако и в двух других методах ограничения не слишком жесткие и, обычно, на практике можно применять любой метод.

2) Все три метода примерно одинаковы и очень просты.

3) Скорость сходимости в методе половинного деления -геометрическая прогрессия со знаменателем 1/2 , в методе итерации -со знаменателем q, а метод Ньютона, как правило, дает сходимость со скоростью, превышающей скорость сходимости любой геометрической прогрессии. Во всех случаях скорость сходимости очень высока.

ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ

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

Постановка задачи интерполирования.

На отрезке (a, b) в n+1 точке (узлах интерполяции) a=X0 < X1 < X2 <...< Xn=b

заданы значения Yi функцииY=f(X). Требуется подобрать вспомогательную функцию (x) (интерполяционную функцию или интерполянту) простого вида, для которой:

  1. (Xi)=Yi при i=0,1,2,3,...,n

  2. (X)f(X) при всех остальных значениях X[a,b].

Основной целью процесса интерполирования является получение быстрого и экономичного алгоритма вычисления приближенного значения функции во всех точках отрезка [a,b].

Формулировка задачи не является строго математической, поскольку в нее входят, например, слова "функция простого вида", или (X)f(X). Главные вопросы здесь -как выбрать интерполянту и как оценить точность приближения функции f(X) на отрезке [a,b].

Ответ на вопрос о точности, без каких-либо дополнительных ограничений на функцию f(X), дать нельзя, поскольку легко привести примеры совершенно непохожих друг на друга непрерывных функций, которые задаются таблично одинаковым способом. Поэтому при оценке точности налагаются ограничения на гладкость функции, что мы и увидим позже.

Рассмотрение вопроса о виде интерполирующей функции (X) привело к созданию целой теории приближений, весьма сложной и большой по объему. Поэтому мы ограничимся рассмотрением лишь простейших случаев: линейной интерполяции и интерполяции многочленами.

Линейная интерполяция.

При линейной интерполяции строится ломаная, которая проходит через точки (Xi;Yi), i=0,1,2,...,n, т.е. совпадающая с искомой функцией в узлах интерполирования и линейная на каждом участке(Xi;Xi+1) при i=0,1,2,...,n-1.

Ясно, что при Xi<=X<=Xi+1 значения построенной функции (X) будут вычисляться по формуле (X)=Yi+(X-Xi) (Yi+1 -Yi)/(Xi+1 -Xi).

Упражнение 2.1 Составить программу для определения значения функции при линейной интерполяции.

Если сетка узлов достаточно плотная на отрезке [a,b], а функция f(X) гладкая, то точность этого метода вычисления приближенного значения функции f(X) вполне удовлетворительна, поэтому в инженерной практике метод линейной интерполяции весьма распространен. Однако, при решении других задач, таких, как задача численного дифференцирования, погрешности данного метода многократно возрастают и перестают быть удовлетворительными.

Интерполяция многочленом.

Единственность интерполяционного многочлена n-й степени.

Другой вариант интерполирования - искать функцию в виде многочлена степени n:

(X)=Pn(X)=CnXn+Cn-1Xn-1+..... +C1 X+C0

Условия совпадения значений интерполирующей функции в точках Xi с величинами Yi примет вид системы: C0+C1X1 +... +CnX1n=Y1

C0+C1X2 +... +CnX2n=Y2

………………………………………….

C0+C1Xn +... +CnXnn=Yn

(n+1)-го линейного уравнения с n+1 неизвестным.

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

Построение вспомогательных многочленов Лагранжа.

Для того, чтобы записать интерполяционный многочлен в форме Лагранжа, сначала строят вспомогательные многочлены L0(X), L1(X),..., Ln(X), каждый из которых является многочленом степени n и удовлетворяет условиям:

hello_html_30ffd7f2.gif, i, j = 0,1,2,..,n.

У каждого из вспомогательных многочленов, тем самым, мы знаем n корней, например, у L2(X) корнями являются X0, X1, X3 ..., Xn. Kaк известно, многочлен Li(X) по корням можно записать в виде

Li(X)=Ai(X-X0)...(X-Xi-1)(X-Xi+1)...(X-Xn)= Ai hello_html_m4a41c38b.gif

Чтобы определить величину Ai, остается еще одно условие Li(Xi)=1, откуда:

hello_html_1a5bbf94.gif

Построение многочлена Лагранжа.

Зная вспомогательные многочлены, легко построить и искомый многочлен в виде их линейной комбинации: hello_html_m23e190b8.gif

В самом деле, степень Рn(х) не выше n, a подставляя в эту формулу значения Х=Хj, получаем: Рn (Xj)=Уj при j=0,1,2,...,n.

Поскольку ранее мы установили, что многочлен степени n, удовлетворяющий условиям интерполяции в узлах единственен, то построенный многочлен Рn(X) и является искомым. Окончательно, он запишется в виде:

hello_html_m21d31a1d.gif

Упражнения: Пользуясь формулой (2.1) выписать интерполяционный многочлен в форме Ньютона для функции, заданной таблицей:

(2.2)

X

1

2

3

(2.3)

X

-1

0

1

2

y

2

3

6

y

2

2

2

8


Оценка точности формулы (2.1) проводится при предположении, что исходная функция f(x) является (n+1) раз дифференцируемой и мы знаем максимум модуля ее (n+1)-ой производной Mn+1. Как уже отмечалось выше, без дополнительных ограничений на гладкость функции никаких оценок произвести нельзя.

Оценка погрешности.

Итак, оценим погрешность формулы (2.1) в какой-нибудь точке Х[a,b], т.е. будем оценивать R(X),где R(x)=f(x)-Pn(x)

Обозначим многочлен степени (n+1) с корнями в узлах интерполирования через w(x):

hello_html_m3a4eabcd.gif

и введем вспомогательную функцию: F(x)=f(x)-Pn(x)-b w(x) (2.2)

При этом коэффициент b в формуле (2.2) мы выберем так, чтобы выполнялось условие

F(X)=0, т.е. f(X)-Pn(X)=b w(X) или R(X)=b w(X) (2.3).

Мы можем без ограничений общности считать, что точка Х не совпадает ни с одним из узлов Хi, поскольку в них погрешность равна 0. В этом случае вспомогательная функция обращается в нуль не менее (n+2) раз на отрезке [a,b]: в точке X и в узлах интерполяции, т.к. w(Xi)=0 и f(Xi)= Pn(Xi).

Используем теорему Ролля, которая утверждает, что между любыми двумя нулями дифференцируемой функции найдется нуль производной, видим, что первая производная F'(x) должна обращаться в нуль на отрезке [a,b] не менее (n+1) раз.

Аналогично, вторая производная F''(x) обращается в нуль не менее n-раз на отрезке [a,b] и т.д.

Рассуждая подобным образом, мы установим, что функция F(n+1)(x) обязательно обращается в нуль хотя бы один раз на отрезке [a, b].

Пусть F(n+1)(d)=0. Дифференцируя формулу (2.2) (n+1) раз, получаем:

F(n+1)(x)=f(n+1)(x)-0-b(n+1)!

откуда легко видеть, что:

f(n+1)(d)=b(n+1)!, или b=f(n+1) (d)/(n+1)!

Подставляя полученное выражение в (2.3), видим:

R(x)=f(n+1)(d)w(x)/(n+1)!,

откуда уже легко произвести нужную оценку

hello_html_m66e20f08.gif (2.4)

справедливую для всех точек отрезка [a,b].

Упражнения: Пользуясь формулой (2.4) произвести оценку точности интерполяции при Х=1.5 в условиях:

2.4. Упражнения (2.2) и предположения M3 < 10 на [1,3]

2.5. Упражнения (2.3) и предположения M4 < 16 на [-1,2]

Преимущество данного метода наглядно проявляется при малом количестве узлов и достаточно гладкой функции. Вычисления на ЭВМ здесь организуются сравнительно просто.

Упражнение 2.6. Составить программу на одном из языков для вычисления значения интерполяционного многочлена в форме Лагранжа (формула(2.1)).

Упражнение 2.7. Дополнить предыдущую программу таким образом, чтобы в случае, когда известен максимум (n+1)-ой производной исходной функции, вычислялась оценка погрешности.

Сплайн-интерполяции.

Помимо описанных методов, существуют и широко распространены на практике приближения функций с помощью СПЛАЙНОВ.

Обычно они применяются когда количество узлов n велико и применять формулу (2.1) невыгодно, а линейная интерполяция не дает желаемых результатов (например при решении задачи численного дифференцирования в узлах). В этом случае выбирают небольшое число К и на каждом отрезке [ Xi,Xi+1] строят свой многочлен степени К, следя за тем, чтобы в узлах Хi разные многочлены "сшивались" гладким образом, например так, чтобы совпадали не только их значения, но и значения их первой, второй, (к-1)-ой производной. Получившаяся при этом функция является, как говорят, кусочно-полиномиальной и называется сплайном.

ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ ФУНКЦИЙ

Хорошо известны многочисленные примеры задач из различных отраслей механики, геометрии, физики, и т.д., которые приводят к необходимости вычисления определенных интегралов функции одной переменной на некотором отрезке. Однако, даже в том случае, когда функция задана аналитически, не всегда возможно вычисление точного значения интеграла с помощью формулы Ньютона-Лейбница. Так, нельзя выразить в элементарных функциях первообразные функции sin(x)/x (интегральный синус) или функции e-x*x, которая играет фундаментальную роль в теории вероятностей. Если же функция задана таблично, то решение аналитическими методами вообще невозможно. Во всех этих случаях (а также и тогда, когда интеграл можно вычислить по формуле Ньютона-Лейбница, но вычисления первообразных весьма сложны и громоздки) на помощь приходят численные методы интегрирования, которые позволяют вычислить ответ с нужной точностью простыми методами, почти не зависящими от способа задания функции.

Формулы, по которым происходят эти вычисления называют обычно формулами численного интегрирования или КВАДРАТУРНЫМИ формулами. Они, в общем случае имеют вид:

hello_html_3eaa5c42.gif (3.1)

где точки Xi[a,b] называются узлами квадратурной формулы, а коэффициенты Сi -весами.

Общая схема

построения различных методов численного интегрирования такова:

1.Отрезок [a,b] разбивают на k равных частей:

a=d01<…k=b, di=a+i*h, где h=(b-a)/k.

2.Интеграл по всему отрезку [a,b] разбивается на сумму интегралов по получившимся отрезкам [di,di+1] при i=0,1,2,…,k-1.

3.На каждом из маленьких отрезков интеграл приближенно вычисляют по формулам (3.1),причем узлы и веса при этом выбираются по одинаковому закону, который мы будем называть ШАБЛОНОМ квадратурной формулы. Количество узлов в шаблоне обычно колеблется от 1 до 5, а самый широко распространенный на практике метод Симпсона имеет в шаблоне 3 узла.

Как правило, при построении шаблона квадратурной формулы узлы выбираются равномерно распределенными по отрезку, а веса получаются при интегрировании вспомогательных многочленов Лагранжа с выбранными узлами. Построенные таким образом формулы носят общее название формул Ньютона-Котеса.

Поясним правило определения весов в формулах Ньютона-Котеса

hello_html_5e5c9de8.gif

Здесь функция f(x) заменяется на интерполяционный многочлен Рn(X), а он записывается в виде линейной комбинации вспомогательных многочленов Лагранжа, которые не зависят от функции f(X) (!).

Рассмотрим кратко наиболее простые квадратурные формулы.

МЕТОД ПРЯМОУГОЛЬНИКОВ.

Шаблон интегрирования содержит один узел, интерполяционный многочлен имеет нулевую степень. Узел выбирают в середине отрезка (возможен выбор узла и в каком-нибудь конце отрезка, но точность при этом будет хуже). Узел Х0 на отрезке [di,di+1] задается формулой Х0=(di+di+1)/2=a+(i+0.5)*h, a интеграл заменяется на выражение h*f(X0).

Упражнение 3.1.Выяснить геометрический смысл такой замены.

Квадратурная формула метода прямоугольников имеет вид:

hello_html_m504e6c1d.gif

МЕТОД ТРАПЕЦИЙ.

Шаблон содержит два узла, которые расположены по краям отрезка [di,di+1], интерполяционный многочлен имеет первую степень. На отрезке [di,di+1] узлы задаются формулами: Х0=di=a+ih; X1=a+(i+1)*h, где i=0,1,2,...,k-1.

Формула шаблона метода трапеций принимает вид:

hello_html_7410592b.gif

Упражнение 3.2.Выяснить геометрический смысл полученной формулы.

Упражнение 3.3.Пользуясь правилом получения весов, вывести самостоятельно формулу шаблона метода трапеций.

Складывая, получаем квадратурную формулу метода трапеций:

hello_html_832dceb.gif

МЕТОД СИМПСОНА.

Шаблон содержит 3 узла, которые расположены по краям и в середине отрезка [di,di+1]; интерполяционный многочлен имеет вторую степень. Геометрический смысл метода в том, что заменяем график функции на параболу, пересекающуюся с ним в концах и середине отрезка, а площадь криволинейной трапеции, соответственно, - на площадь под параболой.

Для того, чтобы вычислить значения весов мы произведем сдвиг отрезка длины h к началу координат (замена переменной, при которой интегралы от вспомогательных многочленов Лагранжа не изменяются) и будем считать, что узлы – Х0=-0.5h, X1=0, X2=0.5h. Тогда вспомогательные многочлены Лагранжа имеют вид:

hello_html_m5dd04d5f.gif

Откуда, интегрируя по отрезку [-h/2,h/2], получаем:

hello_html_3c961817.gif

Итак, формула для ШАБЛОНА метода Симпсона имеет вид:

hello_html_73ffe9b4.gif

Складывая получившиеся отрезках [di,di+1] результаты, имеем:

hello_html_m7bf730e0.gif

Упражнение 3.4.Написать на одном из языков программу численного интегрирования каждым из трех методов.

ПРИМЕР. Вычислим hello_html_m775bfe6.gif методом прямоугольников, трапеций и Симпсона при n=2 и сравним погрешности вычислений (точный ответ равен 6.4).

В методе ПРЯМОУГОЛЬНИКОВ имеем: Ih(f(0+0.5h)+f(0+1.5h))=f(0.5)+f(1.5)=82/16.

При этом получаем погрешность 6.4 - 5.125 =1.275

В методе ТРАПЕЦИЙ имеем: Ih/2(f(0)+f(2))+h*f(0+h)=1/2*(0+16)+f(1)=8+1=9.

Погрешность получается равной 2.6.

В методе СИМПСОНА имеем: Ih/6(f(0)+f(2))+h/3*f(0+h)+2h/3*(f(0+0.5h)+f(0+1.5h)) =16/6+1/3+2/3(82/16)=3+41/126.417

Погрешность получается равной 6.417-6.4=0.017

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

Теоретические оценки погрешности для представленных трех методов следующие:

для метода прямоугольников |r| M2*(b-a)*h2/24;

для метода трапеций |r| M2*(b-a)*h2/12;

для метода Симпсона |r| M4*(b-a)*h4/180.

,где М2 и М4 –соответственно максимумы модуля второй и четвертой производных интегрируемой функции на отрезке интегрирования. Однако в реальных задачах, как правило, бывает затруднительно или совсем невозможно пользоваться этими формулами, поскольку значение максимумов производных трудно, а порой и невозможно вычислить или даже оценить.

Метод двойного счета.

Задача 3.1. Доказать, что методы прямоугольников (с узлом в середине отрезка) и трапеций дают точный результат на всех линейных функциях, но не на всех квадратичных функциях, а метод Симпсона дает точный результат на всех многочленах третьей степени, но не четвертой.

Более коротко, принято говорить, что первые два метода являются методами второго порядка точности и погрешность r удовлетворяет соотношению |r|=О(h2), a метод Симпсона метод четвертого порядка точности, а его погрешность |r|=О(h4).

В частности, это означает, что при уменьшении шага h, например, в 5 раз точность первых двух методов должна улучшиться примерно в 25 раз, а метода Симпсона -в 625 раз.

Исходя их этих соображений, на практике применяют следующий метод слежения за точностью (который называют методом двойного счета): вычисляют ответы по методу Симпсона при n и 2n отрезках и за погрешность последнего ответа берут разность ответов, деленную на 15. Для пояснения данного правила полезно доказать следующее

Упражнение 3.4. Обозначим ответ, полученный при вычислениях интеграла по методу Симпсона при n шагах через In, а при 2n шагах -через I2n, точный же ответ обозначим I. Доказать, что из неравенства |In-I|16|I-I2n| вытекает неравенство |In-I|1/15*|In-I2n|.

Упражнение 3.5. Сформулируйте и докажите метод двойного счета при оценке погрешности вычислений по методу трапеций.

Задача 3.2.Вывести шаблон и квадратурную формулу метода трапеций, если расположить узлы на отрезке [0,h] в точках 0.25h и 0.75h. Как связан получившийся метод и метод прямоугольников? Объясните эту связь геометрически.

Упражнение 3.6.Выведите шаблон квадратурной формулы с тремя узлами, расположенными на отрезке [0,h]

a) в точках h/4, h/2, 3h/4 б) в точках h/6, h/2, 5h/6.

ПРИБЛИЖЕННЫЕ РЕШЕНИЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

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

ПОСТАНОВКА ЗАДАЧИ

Задано уравнение Y'=f(x,Y) и начальное условие Y(х0)=Y0. Требуется найти с заданной степенью точности приближенное решение Y=Y(х), удовлетворяющее начальному условию и уравнению на некотором отрезке [a,b],где a=X0.

Метод Пикара.

Напомним известные теоремы Пикара и Пеано о существовании и единственности решения данной задачи (задачи Коши).

Теорема ПЕАНО утверждает, что решение задачи Коши существует в некоторой окрестности точки Хо, если функция f(x,Y) непрерывна в окрестности точки (X0,Y0).

Теорема ПИКАРА гласит, что если не только функция f(x,Y), но и ее частная производная f'у(x,Y) также непрерывна в окрестности точки (Х00), то решение задачи Коши единственно на некотором отрезке, содержащем точку Х0.

Доказательство теоремы Пикара следует из общего принципа сжимающих отображений, оно весьма непросто, но обладает существенным преимуществом -оно конструктивно. Причем последовательность функций Yn(x), которая строится в нем, сходится к решению равномерно на отрезке со скоростью геометрической прогрессии. В методе Пикара последовательность функций Yn(x) строится по рекуррентной формуле:

hello_html_62b31c2.gif при n= 0,1,2,...,

а за нулевое приближение берется константа Y0: Y0 (х)Y0.

Для того, чтобы стало понятно происхождение этой рекуррентной формулы, заметим, что интегральное уравнение

hello_html_398cbf1e.gif

эквивалентно исходной задаче Коши, поскольку любая функция Y(х), являющаяся его решением, удовлетворяет начальному условию Y(Хо)=Yо и уравнению Y'(х)=f(x,Y(х)) и наоборот.

Вопрос: Почему это действительно так?

Пример 4.1 Применим метод Пикара для решения уравнения Y'=Y с начальным условием Y(0)=1. Такая задача эквивалентна поиску решения интегрального уравнения Y=1+Y(t)dt.

В качестве начального приближения берем функцию Yо=1.

Тогда Y1=1+Yо(t)dt= 1+dt= 1+x.

Далее, Y2= 1+Y1(t)dt= 1+(1+t)dt= 1+x+x2/2.

Y3= 1+Y2(t)dt= 1+(1+t+t2/2)dt= 1+x+x2/2+x3/6.

Можно убедиться, что Yn= 1+х+x2/2+ ... +xn/n!.

Упражнение 4.1.Доказать последнее равенство строго, используя принцип математической индукции.

Упражнение 4.2.В примере 4.1 найти точное решение Y(Х) и оценить скорость равномерной сходимости Yn(x) -> Y(Х) на отрезке [0,1].

В целом, приближенные методы решения обыкновенных дифференциальных уравнений можно разбить на 3 типа:

  • аналитические, позволяющие получить приближенное решение Y(х) в виде формулы,

  • графические, дающие возможность приближенного построения графика решения Y(х),т.е. интегральной кривой,

  • численные, в результате применения которых получается таблица приближенных значений функции Y(х),

хотя такое деление и несколько условно.

Кроме метода Пикара, к аналитическим методам относится и

метод разложения неизвестной функции Y(х) в ряд,

на котором мы сейчас остановимся.

Напишем формальное разложение Y(Х) в ряд Тейлора в точке а:

hello_html_m1250da6e.gif

В это равенство входят производные неизвестной функции Y(Х) в точке а, однако именно в этой точке, пользуясь условиями задачи, мы можем последовательно найти любое число производных и получить необходимое приближение решения. В общем виде это выглядит так: Yо(а)=Y(а)= Yо; Y'(а)=f(a,Y(a))= f(a,Yo)

Дифференцируя данное нам уравнение по Х ,получим

Y''(Х)=f'х(x,Y(х))+f'у(x,Y(х))*Y'(х), откуда Y''(а)= f'х(а,Yо)+f'у(a,Yо)*f(a,Yо).

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

Пример 4.2.Выпишем первые члены разложения в ряд функции Y(x), удовлетворяющей уравнению Y'=2хY и начальному условию Y(0)=1.

Ясно, что Y(0)=1 и Y’(0)=2*0*1= 0. Далее, Y''(х)=2Y+2х*Y'(х), откуда Y''(0)=2.

Y'''(х)=2 Y'(х)+2 Y'(х)+2х*Y''(х)= 4Y'(х)+2хY''(х), откуда Y'''(0)=0.

Y(4)(х)=4Y''(х)+2хY'''(х), откуда Y(4)(0)=6.

Получаем приближенное решение Y(х)1+х2+0.5х4.

Упражнение 4.3.Пользуясь формулой Лейбница для нахождения n-ой производной произведения функций, написать разложение искомой в примере 4.2 функции в ряд Тейлора.

Упражнение 4.4.Найти точное решение в примере 4.2 и оценить качество приближения в примере 4.2 на отрезке [-0.5,0.5].

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

Среди ГРАФИЧЕСКИХ рассмотрим

метод Эйлера.

Суть его состоит в последовательном построении ломаной, начинающейся в точке (Хо,Yо), заданной начальным условием и дающей приблизительный вид графика искомой функции Y(х). Для построения первого (а затем и каждого следующего) участка ломаной в этом методе мы вычисляем значение f(Xo,Yо), проводим прямую из данной точки с полученным угловым коэффициентом. Поскольку Y'(Хо)=f(Хо,Yо), то эта прямая будет касательной к интегральной кривой в точке (Хо,Yо). Поэтому мы и заменяем часть графика функции на отрезок касательной к ней. Далее, из новой полученной точки мы делаем следующий такой же шаг и т.д.

Метод Эйлера хорош тем, что он прост и нагляден, но к сожалению , он очень плох в смысле точности приближения и дает лишь приблизительный вид интегральной кривой.

Говоря о численных методах решения обыкновенных дифференциальных уравнений, мы ограничимся еще более частным случаем постановки задачи, в которой требуется лишь определить значение неизвестной функции Y(х) в одной точке b.

Общая схема численных методов.

1.Делим отрезок [a,b] на n-равных частей точками а=Xo12<…n=b или Xi=a+ih

2.Последовательно, при i=0,1,2,…,(n-1) осуществляем переход от точки (Хi,Yi) к точке (Хi+1,Yi+1) по формуле Yi+1=Yi+Уi, где на каждом отрезке величина Уi вычисляется по одному и тому же закону, задающему метод решения уравнений.

Метод Эйлера, который мы рассматривали как графический, легко интерпретировать и как численный метод. Из описания этого метода сразу же видно, что приращение Yi вычисляется как линейное приращение функции. На отрезке длины h формула для приращения функции примет вид Yi=h f(Xi,Yi), откуда и получаем закон перехода в методе Эйлера: Y i+1=Yi+hf(Xi,Yi).

Как уже отмечалось, погрешность этого метода очень велика, она достигает величин порядка h, т.е. метод Эйлера -первого порядка точности. Для улучшения точности вычислений применяют многошаговую систему перехода от точки (Xi,Yi) к следующей.

методы Рунге-Кутта

Например, в одном из усовершенствований метода Эйлера, который также называют методом Рунге-Кутта второго порядка, переход осуществляют в два этапа по формулам:

Zi = Yi +h/2*f(Xi,Yi) Yi+1=Yi+h*f(Xi+h/2,Zi).

При этом получается погрешность порядка h2.

А самый распространенный на практике метод - метод Рунге-Кутта четвертого порядка, в котором точность имеет порядок величины h4, а переход к следующей точке осуществляется с помощью четырех вспомогательных величин:

k1= h*f(Xi,Yi)

k2= h*f(Xi+h/2,Yi+k1/2)

k3= h*f(Xi+h/2,Yi+k2/2)

k4= h*f(Xi+h,Yi+k3)

После вычисления этих вспомогательных величин переход от точки (Xi,Yi) к следующей точке осуществляется по формуле Yi+1=Yi+1/6*(k1+2k2+2k3+k4).

Упражнение 4.5. Выяснить геометрический смысл перехода к следующей точке по формулам усовершенствованного метода Эйлера.

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

Упражнение 4.6. Выписать и объяснить формулы оценки точности в методах Рунге-Кутта второго и четвертого порядков.

Поясним происхождение формул в методах Рунге-Кутта. Для получения закона вычисления значения Y(x) в каждой следующей точке поступают приблизительно так: выписывают разложение неизвестной функции в ряд Тейлора в точке Xi, как мы проделывали это выше, затем берут несколько первых членов этого разложения, и преобразуют полученную формулу Тейлора. После подставления Xi вместо переменной X и получают окончательное правило перехода к следующей точке.

Легко убедиться, что при выписывании разложения в ряд Тейлора только до линейного члена и подстановки значения X мы получим формулу метода Эйлера, т.е. и он является частным случаем общих методов Рунге-Кутта.

Пример 4.3. Применим формулы разобранных методов для нахождения значения функции Y(x) в точке 1, если эта функция удовлетворяет уравнению y'=y с начальным условием y(0)=1.

При решении методом Эйлера (n=2) имеем:

Y1=Y0+hf(X0,Y0)=1+0.5f(0,1)=1.5, Y(b)=Y2=Y1+hf(X1,Y1)=1.5+0.5f(0.5,1.5)=2.25.

При решении методом Рунге-Кутта 2-го порядка (n=1) имеем:

Z0=Y0+h/2*f(X0,Y0)=1+0.5f(0,1)=1.5, Y(b)=Y1=Y0+hf(X0+h/2,Z0)=1+f(0.5,1.5)=2.5.

При решении методом Рунге-Кутта 4-го порядка (n=1) имеем:

k1=h*f(X0,Y0)= 1*f(0,1)= 1

k2=h*f(X0+h/2,Y0+k1/2)= 1*f(0.5,1.5)= 1.5

k3=h*f(X0+h/2,Y0+k2/2)=1*f(0.5,1.75)=1.75

k4=h*f(X0+h,Y0+k3)= 1*f(1,2.75)=2.75

Y(b)=Y1=Y0+1/6*(k1+2k2+2k3+k4)=1+1/6*(1+3+3.5+2.75)=65/24

Упражнение 4.7. Найти точный ответ и сравнить погрешности, полученные при решении тремя различными методами.

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ

Постановка задачи и ее качественный анализ.

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

Общей ЗАДАЧЕЙ здесь является нахождение функции определенного вида, которая наилучшим образом отражает зависимость между величинами. Важнейшее отличие постановки данной задачи от задачи интерполирования состоит в том, что не требуется обязательное совпадение данных, полученных в результате измерений со значениями искомой функции в выделенных точках.

Такая постановка задачи кажется нам более естественной, поскольку:

  • результаты измерений могут быть неточными,

  • выделенные точки (узлы), как правило, ничем не отличаются от всех остальных и непонятно, почему именно в них мы должны требовать точного совпадения данных.

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

  1. Максимальное по модулю отклонение искомой функции в узлах от данных значений.

  2. Сумма модулей отклонений искомой функции в узлах от данных значений.

  3. Сумма квадратов отклонений искомой функции в узлах от данных значений.

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


ПОСТАНОВКА ЗАДАЧИ.

Дана таблица зависимости функции Y от аргумента X:

Х

Х1

Х2

………

Хn

У

У1

У2

………

Уn


Надо среди функций одного из указанных ниже видов определить такую (найти значения соответствующих параметров), что сумма квадратов разностей значений этой функции в узлах и величин Yi минимальна.

Обычно ограничиваются функциями одного из следующих видов:

  1. Y=ax+b

  2. Y=ax2+bx+c (реже полином более высокой степени)

  3. Y=axn

  4. Y=a ex

  5. Y=1/(ax+b)

  6. Y=a ln(x)+b

  7. Y=a/x+b

  8. Y=x/(ax+b)

Нахождение наилучшей линейной приближающей функции.

Разберем подробно решение задачи, когда решение ищется в виде линейной функции (вид1). Цель - определить коэффициенты a и b таким образом, чтобы величина

hello_html_7a9c3efb.gif

приняла наименьшее значение.

Функция F(a,b) представляет из себя многочлен второй степени относительно величин a и b с неотрицательными значениями, поэтому решение всегда существует. Более того, оно единственно, если узлов больше одного и все они разные.

Задача 5.1. Почему это действительно так? Какую поверхность задает F(a,b)?

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

hello_html_m377ec437.gif

Это система двух линейных уравнений с двумя неизвестными a и b.

Перепишем ее в следующем виде:

hello_html_383df4e1.gif

Введем стандартные в статистике обозначения для моментов:

hello_html_5162668c.gif

Тогда наша система перепишется в следующем виде:

hello_html_m73065efe.gif

которая решается стандартным образом.

Далее, осталось отметить, что раз критическая точка одна, а мы предварительно определили, что у нашей задачи решение есть, то задача решена полностью.

Разберем ПРИМЕР 5.1 нахождения наилучшей линейной функции.

Пусть зависимость задана таблицей

X

-3

-1

1

3

5

Y

3

4

6

8

10

Для ручного вычисления моментов Mx, My, Mxx, Mxy построим таблицу:


X

Y

X2

XY


-3

3

9

-9


-1

4

1

-4


1

6

1

6


3

8

9

24


5

10

25

50

Сумма

5

31

45

67

Среднее значение (М)

1

6.2

9

13.4

Отсюда получаем систему

9a+b=13.4 a=0.9

a+b=6.2 или b=5.3

Итак, наилучшая линейная функция имеет вид y=0.9x+5.3

Упражнение 5.1. Проверьте, что если исходные данные удовлетворяют линейной зависимости Yi=а*Xi+b, то и коэффициенты a и b, полученные при решении указанным методом совпадут с исходными.

Упражнение 5.2. Аналогично приведенному выше методу проделайте выкладки и получите систему уравнений для поиска коэффициентов a, b, c при подборе эмпирической квадратичной зависимости (функция вида 2).

Сведение поиска функций другого вида к поиску линейной функции.

При поиске функций другого вида (3-8) задача сводится к рассмотренной выше задаче нахождения наилучшей линейной функции. Для этого производится некоторая замена переменных, которая подбирается таким образом, чтобы вновь полученная задача свелась к нахождению линейной зависимости, а после применения описанной конструкции происходит обратная замена.

Рассмотрим на конкретных примерах, как это происходит.

При поиске, скажем, функции y=1/(ax+b) (вид 5) для сведения задачи к линейной мы производим замену t =1/y, после которой задача сводится к нахождению наилучшей линейной функции t=ax+b. А коэффициенты, найденные при ее решении и будут искомыми в первоначальной задаче. Тем самым, поиск наилучшей функции вида 5 надо осуществлять так:

  1. заменяем в исходной таблице переменную Y на t, а все числа, записанные в нижней строке - на обратные

  2. для получившейся таблицы находим линейную зависимость

  3. получившиеся значения a и b берем без изменения.

Аналогичные действия мы производим при поиске наилучшей приближающей функции вида 6. Но замена, которую необходимо произвести для сведения к линейной задаче, в этом случае имеет вид u=ln(x). Итак, мы получим такое правило поиска наилучшей функции вида 6:

  1. заменяем в исходной таблице переменную X на u, а все числа, записанные в верхней строке - на их логарифмы

  2. для получившейся таблицы находим линейную зависимость

  3. получившиеся значения a и b берем без изменения.

Упражнение 5.3. Провести подобные рассуждения и сформулировать способ решения задачи для функций вида 7.

Для того, чтобы найти наилучшую функцию вида 3, нужно прологарифмировать соотношение y=ахn. При этом получится ln(Y)=ln(a)+n*ln(x), откуда и вытекает способ решения:

  1. заменяем в исходной таблице переменную X на u=ln(X), переменную Y на t=ln(y), а все числа, записанные в таблице - на их логарифмы

  2. для получившейся таблицы находим линейную зависимость

  3. по получившимся значениям a и b находим нужные нам числа применяя формулы n=а, a=eb.

Упражнение 5.4. Провести подобные рассуждения и сформулировать способ решения задачи для функций вида 4.

Упражнение 5.5. Провести подобные рассуждения и сформулировать способ решения задачи для функций вида 8.

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

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

Постановка задачи и ее качественное исследование.

Рассмотрим систему m линейных уравнений с n переменными:

hello_html_m307aa430.gif (7.1)

Систему (7.1) можно записать короче в виде одного матричного уравнения AX=B,

где Х -столбец длины n, B -столбец длины m, А -матрица размерами mхn.

TEOРЕМА 1. Если ранг матрицы А совпадает с рангом расширенной матрицы (А|B), то в этом случае существует решение системы (7.1) и наоборот.

ТЕОРЕМА 2. В случае, когда количество уравнений совпадает с числом неизвестных и определитель A отличен от 0, существует единственное решение системы(7.1).

m=n и det(А)<>0 => решение (7.1) существует и единственно.

Если n>m, то решений (7.1) обычно бесконечное множество (линейное пространство размерности n-rang(A)). Если m>n, то обычно решений нет.

Упражнение 7.1. Приведите пример несовместной системы, у которой m<n.

Упражнение 7.2. Приведите пример совместной системы, у которой m>n.

Далее мы ограничимся рассмотрением частного случая: m=n и det(А)<>0, т.е. случай, когда решение существует и единственно, хотя метод Гаусса, например, носит универсальный характер.

Методы решения систем линейных уравнений можно разбить на две группы: точные методы и приближенные. К точным (прямым) относятся методы, позволяющие за конечное число шагов получить точное решение системы, (т.е. те методы, погрешность которых равна 0). К итерационным относятся методы, при которых строится рекуррентная последовательность векторов, сходящихся к решению. Обычно они применяются, когда применение точных методов затруднено или невозможно, например когда порядок системы – тысячи переменных.

К прямым методам относятся, кроме метода Гаусса, метод квадратного корня для симметричных матриц (или компакт-метод для произвольных), метод Крамера. Последний метод обычно изучается в теории систем линейных уравнений в виду возможности кратко записать решение системы. Пусть D-определитель квадратной матрицы А системы линейных уравнений: D=det(A)0. Пусть D(i)-определитель матрицы, у которой на i-ом месте находится столбец В, а остальные столбцы совпадают с соответствующими столбцами матрицы А. Тогда координаты вектора решения находятся по формулам: Х(i)=D(i)/D.

Упражнение 7.3. Определите по формулам Крамера решение системы и проверьте его:

hello_html_m78582aba.gif

Метод Гаусса

(метод последовательного исключения переменных)

Матрица называется верхнетреугольной, если ниже главной диагонали все элементы равны нулю, т.е. aij=0 при i>j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i<j) равны 0. Матрица называется диагональной, если только на главной диагонали (i=j) стоят ненулевые элементы. Метод Гаусса решения систем линейных уравнений состоит из двух этапов: прямого хода и обратного хода.

Прямой ход.

Это основной этап решения системы уравнений с помощью метода Гаусса. Его суть состоит в приведении исходной расширенной матрицы системы к верхнетреугольной матрице с помощью эквивалентных преобразований (добавление к строке любой линейной комбинации других строк и перестановка строк, т.е. уравнений). Формулы прямого хода соответствуют последовательному выражению переменных из уравнений и подстановке их в последующие уравнения, т.е. их фактическому исключению из последующих уравнений системы. При этом шагом считается исключение одной переменной из всех последующих уравнений системы.

Рассмотрим k-ый шаг прямого хода. На k-ом шаге матрица системы имеет вид:

(а11 а12а1k … a1n | b1)

(0 a22 … a2k … a2n | b2)

(0 … … … … … )

(0 0 … akk … akn | bk)

(0 … … … … … )

(0 0 … ank … ann | bn)

Осталось n-k+1 неизвестных. Чтобы удалить х(k) из последней строчки, например, надо из нее вычесть k-ую строчку с таким коэффициентом, чтобы получить на месте аnk ноль. Для этого коэффициент должен быть равен cnk=ank/akk. Элемент аkk называется разрешающим элементом k-ого шага и должен быть отличен от 0.

Формулы прямого хода

cmk=amk/akk где 1<=k<n

bm=bm-cmkbk, k

aml=aml-cmkakl, k<=l<=n

Обратный ход

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

Формулы обратного хода.

hello_html_m627e1cd7.gif ,откуда получаем:hello_html_m4b6a94db.gif

для k=n,n-1,…,1.

Ручные вычисления по методу Гаусса.

В процессе ручных вычислений по методу Гаусса заполняется таблица, которая состоит из нескольких разделов, соответствующих определенным этапам вычислений. В ней вводится столбец s- сумма всех коэффициентов в строке, столбец - контрольный столбец (на нулевом шаге он заполняется из столбца s, а затем преобразуется вместе со строками по той же формуле, причем, сравнивая его со столбцом s, мы проверяем правильность вычислений, поскольку данные столбцы должны совпадать). На каждом следующем шаге прямого хода в таблице уменьшается как количество уравнений (т.к. на k-м шаге мы меняем только последние n-k уравнений), так и количество неизвестных. При этом один из пустых столбцов таблицы (там должны были бы стоять только нули) мы используем для записи коэффициентов cmk, на которые домножаем k–ю строку перед вычитанием из m–й.

Пример. Решить систему: hello_html_m545efaff.gif

Таблица при ручных вычислениях имеет вид:

___________________________________________

N шага | Матрица А | Св.член | | s

_______ _|_____________|________|____|________

| 3 -1 0 | 1 | 3 | 3

0 | -2 1 1 | 0 | 0 | 0

| 2 -1 4 | 0 | 5 | 5

________|_ ___________|________|_ ___|_______

|-2/3 1/3 1 | 2/3 | 2 | 2

1 | 2/3 -1/3 4 | -2/3 | 3 | 3

______ __|_____________|________|_____|_______

2 | -1 5 | 0 | 5 | 5

________|_____________|_________|____|_______

| х3 = 0 |

| х2 = 2 |

| х1 = 1 |

Регуляризация решения

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

Задача 7.4. Докажите, что в невырожденных системах не может встретиться случай, когда и разрешающий элемент, и все элементы столбца ниже него на каком-то шаге окажутся равными нулю одновременно.

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

___________________________________________

| 1.2357 | 2.1742 | -5.4834 | -2.0735

0 | 6.0696 | -6.2163 | -4.6921 | -4.8388

| 3.4873 | 6.1365 | -4.7483 | 4.8755

___|_________|_________|_________|__________

1 | 4.919 | -16.895 | 22.242 | 5.3462

| 2.8221 | 0.0007 | 10.727 | 10.727

___ |__ ______|_________|_________|__________

2 | | 0.41E-04 | 10.728 | 10.727

___ |_________|_________|_________|__________

| x3 = 0.99991

| x2 = 0.99994

| x1 = 0.99968

___ |_______________________________________

Правильный ответ: х1=1, х2=1, х3=1

Теперь поменяем местами 2-е и 3-е уравнения:

__________________________________________

| 1.2357 | 2.1742 | -5.4834 | -2.0735

0 | 3.4873 | 6.1365 | -4.7483 | 4.8755

| 6.0696 | -6.2163 | -4.6921 | -4.8388

___|_________|__________|_________|__________

1 | 2.8221 | 0.0007 | 10.727 | 10.727

| 4.919 | -16.895 | 22.242 | 5.3462

___|_________|_________|_________|__________

2 | | 24136 | 258930 | 258910

___|_________|_________|_________|___________

| x3 = 0.99992

| x2 = 1.4286

| x1 = 2.9021

___|________________________________________

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

Описание метода Гаусса для вырожденных систем.

Хочется еще раз подчеркнуть, что метод Гаусса приспособлен и для решения вырожденных систем. Отличия при этом невелики. Приведение системы происходит описанным выше методом, но не обязательно к верхнетреугольному виду, а к более общему -ступенчатому. Если на каком-то шаге прямого хода встречается ситуация, когда в столбце не только разрешающий элемент, но и все элементы ниже него равны нулю (переменная как-бы исключилась сама по себе), то мы просто начинаем из этого же уравнения исключать сразу следующую переменную, т.е. переходим к следующему столбцу, не переходя к следующей строке. После окончания прямого хода возможны два варианта:

  • либо мы видим, что полученная система несовместна, когда в одной из последних ненулевых строк все коэффициенты левой части равны 0, а свободный член – нет

  • либо система имеет бесконечное множество решений, которые можно получать следующим общим способом – задать произвольные значения всем «свободным» переменным, которые были пропущены в процессе исключения, т.е. «исключились сами по себе» и вычислить значения всех остальных переменных по формулам обратного хода.

Применения метода Гаусса.

Метод Гаусса является одним из эффективных методов решения различных задач линейной алгебры.

Нахождение определителя матрицы.

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

Нахождение обратной матрицы

Пусть А' - обратная матрица, т.е. А*А'=Е. Для того, чтобы найти обратную матрицу, каждый столбец матрицы А' обозначим как неизвестный вектор Х(1),Х(2),….Тогда для решения матричного уравнения А(Х(1)Х(2)...)=Е можно N раз решить систему линейных уравнений методом Гаусса с неизвестным вектором Х(i) и правым столбцом – одним из столбцов единичной матрицы.

Второй метод нахождения обратной матрицы: выпишем матрицу (А|Е), в которой n строчек и 2n столбцов. Проделав прямой ход, получим (\ # # | )

(0 \ # | A`)

(0 0 \ | ),

где А` - промежуточная матрица (\ # #)

Обратный ход заключается в том, что матрицу (0 \ #) приводят

к единичной (0 0 \)

В результате получим матрицу ( Е|А').

Нахождение ранга матрицы.

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

Определение совместности системы.

Поскольку совместность системы означает совпадение рангов матрицы А исходной системы и расширенной матрицы (А|B), то проще всего поступить аналогично предыдущему пункту. Берем расширенную матрицу и приводим к ступенчатому виду. Если есть строки с нулевой левой частью и ненулевым свободным членом, то система несовместна, если нет – совместна.

МЕТОД КВАДРАТНОГО КОРНЯ

Условие применимости метода квадратного корня.

Метод квадратного корня является одним из прямых методов решения систем линейных алгебраических уравнений. Однако этот метод не такой универсальный, как метод Гаусса: для применения данного метода матрица системы линейных уравнений должна быть невырожденной (det(А)0) и симметрической: А=Аt ( Аt- транспонированная к А матрица).

(Матрица А является симметрической, если ее элементы, расположенные симметрично относительно главной диагонали, равны между собой, т.е. aij=aji. при всех i,j. Матрица В является транспонированной к матрице А, если ее столбцы совпадают с соответствующими строками А).

Метод квадратного корня сокращает вычисления примерно в 2 раза за счет симметрии.

При выполнении условий невырожденности и симметричности матрицы системы метод квадратного корня уже можно применять, но в процессе вычислений по формулам метода при этом могут возникать комплексные числа. Решение задачи, правда, будет вещественное. Для того, чтобы избежать работы с комплексными числами, мы потребуем от матрицы А выполнения еще одного дополнительного условия: положительной определенности, т.е. все главные миноры А должны быть положительны. (Напомним, что главным минором порядка К квадратной матрицы А называется минор, состоящий из элементов, находящихся на пересечении первых К строк и первых К столбцов матрицы А).

Матричное описание метода квадратного корня.

Основанием для этого метода служит следующая ТЕОРЕМА:

Пусть данная система АХ=В удовлетворяет условию применимости метода квадратного корня. Тогда существует такая верхнетреугольная матрица S, что: StS=A(8.1)

В этом случае исходную систему можно записать в виде (StS)X=B или St(SX)=B. Если обозначить SX=Y, то весь процесс нахождения решения Х можно разбить на три этапа:

  1. Найти матрицу S: StS=A;

  2. Найти Y: StY=B;

  3. Найти X: SX=Y.

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

Нахождение матрицы S («квадратного корня» из А)

Покажем процесс нахождения коэффициентов матрицы S в случае матрицы А размерами 4х4, а потом уже выпишем общие формулы.

Обозначим элементы матрицы S:

hello_html_fe22533.gif


Тогда должно быть выполнено соотношение A=StS, или


hello_html_4c238b00.gifhello_html_m3bca84ec.gif

По правилам умножения матриц получаем систему:

s11*s11 = a11

s11*s12 = a12

s11*s13 = a13

s11*s14 = a14

s12*s12 + s22*s22 = a22

s12*s13 + s22*s23 = a23

s12*s14 + s22*s24 = a24

s13*s13 + s23*s23 + s33*s33 = a33

s13*s14 + s23*s24 + s33*s34 = a34

s14*s14 + s24*s24 + s34*s34 + s44*s44 = a44

из 10 уравнений. На первый взгляд, мы сильно усложнили задачу – вместо линейной системы из 4-х уравнений с 4-мя неизвестными мы должны решать систему из 10 нелинейных уравнений с 10 неизвестными. Однако, и в случае 4х4, и в случае N неизвестных наша система решается очень просто: мы по очереди находим все элементы матрицы S. Из 1-го уравнения найдем s11, потом из 2-го уравнения- s12 и т.д. Таким образом мы построчно определим все элементы искомой матрицы.

ОБЩИЕ ФОРМУЛЫ ДЛЯ НАХОЖДЕНИЯ ЭЛЕМЕНТОВ МАТРИЦЫ S имеют вид:


hello_html_26400e6d.gif, где i=1,2...n

hello_html_m61039a9c.gif, где j=i+1,...,n


Нахождение вспомогательного вектора Y.

Для нахождения вектора Y мы решаем систему StY=B, и получаем:

hello_html_71a19d47.gif, где j=1,2,...,n

Нахождение вектора решения Х.

Для нахождения вектора Х мы решаем систему SХ=Y, и получаем:

hello_html_669bab0.gif, где i=n,n-1,...,1

Пример.

Решим с помощью метода квадратного корня следующую систему:

hello_html_6605b941.gif или hello_html_m8d1b0ad.gif

Заметим, что условие симметричности: выполняется, но если поделить второе уравнение на 4, то оно перестанет выполняться и метод квадратного корня применять будет уже нельзя.


1. Вычисляя по формулам коэффициенты матрицы S, получим:

hello_html_49d4e0fd.gif и hello_html_26da380b.gif


2. Находим координаты вспомогательного вектора:

hello_html_70eb595a.gif ,откуда получаем hello_html_m3044a26d.gif

  1. Находим решение:

hello_html_m6189a809.gif ,откуда получаем hello_html_96ec42.gif

  1. На всякий случай, подставляя Х в исходную систему, убеждаемся в правильности решения.

Компакт-метод.

Как уже отмечалось, метод квадратного корня применим только для систем с симметричной матрицей A. Однако существует так называемый компактный метод, который по сути очень похож на метод квадратного корня, но применим уже к любым невырожденным квадратным системам. При этом суть метода остается той же - разложение матрицы A на произведение верхне-и нижнетреугольной матриц, правда уже не взаимнотранспонированных.

Упражнение 8.1. Вывести самостоятельно матричное описание компакт-метода.

Упражнение 8.2. Вывести самостоятельно формулы для разложения матрицы А системы на произведение верне- и нижнетреугольной матриц.

МЕТОД ПРОСТЫХ ИТЕРАЦИЙ

Данный метод относится к приближенным методам решения систем линейных уравнений. Для его применения необходимо преобразовать исходное уравнение АХ=В к эквивалентному виду Х=АХ+В, (9.1)

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

Упражнение 9.1. Обоснуйте.

Мы будем рассматривать уравнение (9.1) при условии, что его решение существует и единственно, т.е. будем рассматривать только корректную задачу.

Упражнение 9.2. Сформулируйте краткое математическое условие на матрицу А, при котором уравнение (9.1) имеет единственное решение для любого вектора В.

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

Условия применимости метода простых итераций.

Рассмотрим отображение n-мерного евклидова пространства в себя, заданное формулой: Y=AX+B, где А- матрица размерности nхn, X,B,Y Rn. Главный вопрос применимости метода заключается в следующем: в каком случае это отображение будет сжимающим, т.е. существует некоторое число q, 0<q<1, такое что при всех х1 и х2 справедливо:

hello_html_m216dd837.gif

Что надо потребовать от матрицы А, чтобы выполнялось это условие?

Приведем несколько достаточных условий. Для этого вспомним, что основными нормами в пространстве Rn являются

1. hello_html_688a7598.gif, где x=(x1,x2,...,xn)

2. hello_html_66dfecb0.gif

3. hello_html_m256a33ad.gif, где i=1,2,...n

Рассмотрим в исходном пространстве векторов норму hello_html_22a2f022.gif и оценим норму hello_html_m552683e.gif оператора преобразования Y=AX+B через элементы матрицы А.

Оценивать норму мы будем в два этапа: 1. Сначала оценим i-ую компоненту вектора y1-y2.

2. Затем оценим норму всего вектора y1-y2.

Возьмем i-ую компоненту вектора y1-y2 и оценим сверху эту разность по модулю.

hello_html_m6a9a7630.gif

Далее уже легко оценить и норму разности векторов y1-y2:

hello_html_1d053669.gif, где максимум берется при всех i=1,2,…,n

Следствие. Если hello_html_m552683e.gif=махhello_html_m163bb0ee.gif <1, (i=1,2,…,n), то отображение Y=AX+B сжимающее.

Задача. Доказать, что для двух других норм в исходном пространстве получим:

hello_html_59238382.gif, и hello_html_cb06c85.gif, где максимум берется при всех j=1,2,…,n.

Если при этом хотя бы одно из этих чисел меньше 1, то отображение сжимающее.

Описание метода простых итераций.

Вернемся теперь к решению системы линейных уравнений, преобразованной к виду (9.1).

Решить систему - значит найти неподвижную точку Х такую, что если подставить ее координаты в правые части уравнений (9.1), то получим ту же точку Х. Для поиска неподвижной точки сжимающего отображения мы, как обычно, построим рекуррентную последовательность векторов по следующему правилу:

Х0-произвольный, Хk+1 = А Хk + В (9.2)

После построения последовательности векторов посмотрим, сходится ли построенная последовательность. Если да, то она сходится обязательно к решению системы (9.1).

Упражнение 9.3. Докажите.

Сходится последовательность или нет – зависит от матрицы А и начального вектора Х0.

ТЕОРЕМА. Пусть задана система линейных уравнений (9.1) и построена рекуррентная последовательность векторов по правилу (9.2). Если для матрицы А хотя бы одно из чисел q1,q2,q меньше 1, то мы можем утверждать, что последовательность векторов, которую мы построили, обязательно сходится к решению со скоростью геометрической прогрессии со знаменателем q.

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

Упражнение 9.4. Проведите самостоятельно доказательство теоремы.

Из теоремы вытекает соответствующий метод решения системы. Заметим, что при выполнении ограничений на элементы матрицы А последовательность построенных по правилу (9.2) векторов сходится к решению независимо от выбора вектора Х0, но обычно в качестве Х0 выбирают вектор В. Это можно объяснить тем, что если взять Х0=0, то на следующем шаге получится вектор В, т.е. он как бы лежит на пути от 0 к решению системы. Повторим, что у метода итераций есть преимущество перед всеми другими методами: это устойчивый метод.

Условие окончания вычислений.

Замечание. Если ответ надо получить с заданной точностью , то вычисления прекращают на том этапе вычислений, когда начнет выполняться неравенство:

hello_html_mfcf1cc6.gif, причем в качестве величины q берут наименьшую величину из трех вычисленных норм матрицы A, а в качестве нормы пространства Rn- соответствующую норму.

Упражнение 9.5. Обоснуйте условие окончания вычислений в методе простых итераций.

Приведение исходной системы к нужному виду.

Из различных вариантов приведения системы к виду, пригодному для применения метода простых итераций, мы отметим два простых случая, которые нередко встречаются на практике.

Случай диагонального преобладания.

Если в исходной системе все элементы, стоящие на главной диагонали, по модулю больше, чем сумма модулей остальных элементов в этой же строке (столбце) матрицы А, то для приведения к нужному виду в левой части оставляют только диагональные элементы, а остальные переносят в правую часть и каждое уравнение делят на диагональные элементы.

Пример1:

5x1-x2+2x3=13 x1=0.2x2-0.4x3 +2.6

2x1-10x2+4x3=0 x2=0.2x1+0.4x3 +0

x1+2x2+20x3=100 x3=-0.05x1-0.1x2 +5

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

Случай, когда матрица А близка к единичной.

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

Этот случай похож на предыдущий, но обязательно ли матрица, близкая к единичной является матрицей с диагональным преобладанием?.

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

Пример2.

hello_html_643aa0ab.gif hello_html_m1777a0c8.gif

Заметим, что в некоторых случаях удобнее комбинировать оба способа преобразования уравнений исходной системы – деление на диагональные элементы и вычитание из них 1.

Упражнение 9.7 Для матриц из примеров 1 и 2 посчитать их нормы в трех различных метриках пространства Rn и найти минимальную (число q).

Упражнение 9.8. Для системы из примера1, приведенной к нужному виду, взять в качестве Х0 нулевой вектор и построить два следующих вектора итерационной последовательности.

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

Численные методы решения экстремальных задач

Постановка задачи.

Пусть hello_html_278687bc.gif- функция, определенная на некотором множестве hello_html_6a5ca2b.gif. Будем рассматривать задачу минимизации функции hello_html_278687bc.gif. Любая задача максимизации функции hello_html_278687bc.gifна hello_html_7ba38183.gif равносильна задаче минимизации функции hello_html_1f54f85.gifна том же множестве hello_html_7ba38183.gif. Поэтому можно ограничиться лишь изучением задач минимизации.

Классический подход.

Пусть hello_html_278687bc.gifкусочно-непрерывная и кусочно-гладкая функция на отрезке [a, b] ([a, b]X). Это значит, что на [a, b] может существовать лишь конечное число точек, в которых функция hello_html_278687bc.gifлибо терпит разрыв первого рода, либо непрерывна, но не имеет производной. Тогда точками экстремума функции hello_html_278687bc.gifна [a, b] могут быть лишь те точки, в которых выполняется одно из следующих условий: 1)hello_html_278687bc.gifтерпит разрыв; 2)hello_html_278687bc.gifнепрерывна, но производная не существует; 3)производная hello_html_63086ecb.gifсуществует и равна нулю; 4)hello_html_13cf0fed.gifили hello_html_m24918789.gif. Такие точки принято называть точками подозрительными на экстремум. Поиск точек экстремума функции начинают с нахождения всех точек, подозрительных на экстремум. После того, как такие точки найдены, проводят дополнительное исследование и отбирают среди них те, которые являются точками локального минимума (максимума).

Упражнение 1. Запишите достаточное условие того, что подозрительная точка x* [a, b] является точкой локального минимума (максимума).

Чтобы найти глобальный минимум (максимум) функции hello_html_278687bc.gifна [a, b], нужно перебрать все точки локального минимума (максимума) на [a, b] и среди них выбрать точку с наименьшим (наибольшим) значением функции, если таковая существует (если вместо [a, b] имеем дело с R, то следует изучить поведение функции при hello_html_m10c6af6e.gif или hello_html_m5975a39f.gif).

К сожалению, классический метод имеет весьма ограниченное применение. В практических задачах вычисление hello_html_63086ecb.gifзачастую является непростым делом. Например, значения функции hello_html_278687bc.gifопределяется из наблюдений или эксперимента, и получить информацию о её производной крайне трудно. Поэтому важно иметь также и другие методы поиска экстремума, не требующие вычисления производной, удобные для реализации на ЭВМ.

Упражнение 2. Найти точки экстремума функции hello_html_278687bc.gif= sin3(x) + cos3(x) на отрезках [0, 3/4], [0, 2].

Упражнение 3. Пусть hello_html_278687bc.gif= (1 + e1/x )-1 при x0, f(0)=0. Найти точки экстремума этой на отрезках [-1, 0], [-1, 1], [1, 2] и на R.

Поиск экстремумов функций одной переменной является самостоятельной и часто встречаемой задачей. Кроме того, к нему сводится более сложная задача поиска экстремумов функций множества переменных.

Численные методы поиска экстремумов функций одной переменной

Как было уже сказано, в общем случае функция hello_html_278687bc.gif hello_html_m55794c28.gif может иметь несколько экстремумов (минимумов или максимумов). Задача поиска экстремумов сводится к их локализации и уточнению значений hello_html_m5547f17b.gif и hello_html_278687bc.gifв точке экстремума. Все рассмотренные ниже численные методы предполагают, что локализация экстремумов каким-либо образом произведена (например, графически или аналитически) и задача численных методов будет состоять в уточнении полученных результатов с заданной точностью . В дальнейшем для функций одной переменной под экстремумом будем подразумевать минимумhello_html_278687bc.gif. Будем считать, что hello_html_m5547f17b.gif[a,b], где a и b границы интервала поиска. В пределах отрезка [a,b] функция hello_html_278687bc.gifнеобязательно непрерывная, могут существовать разрывы первого рода. Достаточно чтобы функция hello_html_278687bc.gifна отрезке [a, b] была унимодальной, то есть, содержащей на указанном отрезке один минимум.

Метод равномерного поиска.

Этот метод основан на том, что переменной hello_html_m5547f17b.gif присваиваются значения hello_html_7d807d2a.gifc шагом h =const (шагом поиска), где i=0,1,2,… и вычисляются значения hello_html_m337b3bb1.gif в соседних точкаx. Если hello_html_68abf64c.gif, то переменной hello_html_m5547f17b.gifдается новое приращение. Как только становится hello_html_42eac52.gif, поиск останавливается и предпоследняя точка считается ответом.

Выбор hello_html_3fea5f90.gif (начального значения переменной hello_html_m5547f17b.gif) определяется пользователем. Шаг поиска - фактическая погрешность определения результата. При поиске решения на отрезке, обычно в качестве начального приближения берут один из его концов, а при изменении переменной х предусматривается проверка на выход ее за границу отрезка.

Метод поразрядного приближения

является разновидностью метода равномерного поиска и реализуется следующим образом:

  1. Задаем начальное приближение hello_html_11195d79.gif слева от минимума функции hello_html_m337b3bb1.gif и вычисляем hello_html_m2ce573ba.gif, задаем начальный шаг поиска h (выбирается вычислителем), точность определения результата поиска (для переменной hello_html_m5547f17b.gif), берем i=0.

  2. Задаем hello_html_517b8593.gif и вычисляем hello_html_36fe86c0.gif.

  3. Проверяем условие hello_html_68abf64c.gif, если оно выполняется, то идем к пункту 2, увеличивая hello_html_52908ad7.gif на 1.

  4. Проверяем условие |h| . Если оно выполняется, полагаем h = -h/10, увеличиваем hello_html_52908ad7.gifна 1 и идем к пункту 2, т.е. обеспечиваем поиск минимума в другом направлении с шагом h/10.

  5. Выводим на печать полученное значение для переменной hello_html_m5547f17b.gif и функции hello_html_m337b3bb1.gif.

Метод деления отрезка пополам (или метод дихотомии).

Поиск минимумаhello_html_m337b3bb1.gifна отрезке [a, b] на каждом шаге начинается с выбора двух точек hello_html_m41f28790.gif и hello_html_1f8825e3.gif, где hello_html_m20941de0.gif>0-постоянная, являющаяся параметром метода. Величина hello_html_m20941de0.gifвыбирается вычислителем и может определяться целесообразным количеством верных десятичных знаков при задании аргумента hello_html_m5547f17b.gif. Точки hello_html_m7d400f82.gif и hello_html_m143463e.gifрасположены симметрично на [a, b] относительно его середины и при малых hello_html_m20941de0.gifделят его почти пополам. Уточняем положение экстремума с заданной точностью hello_html_363d9209.gif.

Метод реализуется следующим алгоритмом:

  1. Проверяем условие |b-a|<. Если условие выполняется, идем к пункту 6.

  2. Делим интервал поиска [a, b] точками hello_html_355cf9fa.gif и hello_html_1f8825e3.gif.

  3. Для значений hello_html_m7d400f82.gif и hello_html_m143463e.gifвычисляем hello_html_m24393b5f.gifи hello_html_7378e262.gif.

  4. Проверяем условие hello_html_m781ab441.gif. Если оно выполняется, полагаем hello_html_m147d6cf1.gif и идем к пункту 1.

  5. Полагаем hello_html_m181a45a6.gif и идем к пункту 1.

  6. Выводим на печать hello_html_71adf50b.gif и hello_html_m337b3bb1.gif.

Упражнение 4. Зная начальные данные, оценить количество итераций в предложенном методе. Сколько раз вычисляются значения функции hello_html_m337b3bb1.gif?

Метод квадратичной интерполяции

Этот метод основан на замене hello_html_m337b3bb1.gifв промежутке hello_html_14b2fec6.gifквадратичной параболой, экстремум которой вычисляется аналитически. После приближенного нахождения экстремумаhello_html_71d02e7d.gif (максимума или минимума) можно задать hello_html_mf636237.gifи повторить поиск. Таким образом, с помощью итерационной процедуры значение hello_html_71d02e7d.gifуточняется до получения его с заданной точностью hello_html_363d9209.gif.

Алгоритм метода следующий:

  1. Задаем начальное приближение hello_html_3fea5f90.gifдля hello_html_71d02e7d.gifи вычисляем два смежных значения аргумента hello_html_m337b3bb1.gifhello_html_6fa0c206.gifи hello_html_m64aecc8c.gif, где hello_html_cc1127f.gif-полуинтервал поиска.

  2. Вычисляем три значенияhello_html_m2ce573ba.gif,hello_html_m24393b5f.gif,hello_html_7378e262.gif.

  3. Находим коэффициенты параболы hello_html_38aa7671.gif,c (считая, что hello_html_m337b3bb1.gifна указанном отрезке представляет собой параболу hello_html_7b9d742e.gif) и по найденным коэффициентам вычисляем положение экстремума hello_html_m7fbf1aae.gif.

  4. Проверяем условие |x*-x0|<. Если условие не выполняется, задаем x0=x* и идем к пункту 1. Если выполняется, считаем x* найденным с заданной точностью , идем к пункту 5.

  5. Выводим на печать x* и f(x*).

Упражнение 5. Вывести формулы пункта 3 алгоритма.

Метод золотого сечения

Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка.

Золотое сечение отрезка [a, b] производится двумя точками hello_html_362cc3f6.gifи hello_html_m2dbff2b2.gif, где hello_html_275b5d6.gif.

Точки x1 и x2 расположены симметрично относительно середины отрезка и выполняется

hello_html_m7c71d617.gif и hello_html_4a6e131a.gif.

Упражнение 6. Точка x1 в свою очередь производит золотое сечение отрезка [a, x2]. Аналогично точка x2 производит золотое сечение отрезка [x1, b]. Доказать это.

Опираясь на это свойство золотого сечения, предложен следующий метод минимизации унимодальной функции hello_html_278687bc.gifна отрезке [a, b]. Его суть - деление интервала поиска минимума по правилу золотого сечения, вычисление значения hello_html_278687bc.gifв точках деления, сравнение значений и отбрасывание той части интервала, на которой заведомо отсутствует минимум. Точка x1 производит золотое сечение [a, x2], точка x2 - золотое сечение отрезка [x1, b]. Поэтому на оставшемся интервале нужно определить одну точку, производящую золотое сечение. Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет меньше заданной точности . На каждом шаге длина нового интервала неопределенности равна 0,618 длины старого интервала и на каждом шаге вычисляется лишь одно значение hello_html_278687bc.gif, а не два, как в методе деления отрезка пополам.

Упражнение 7. Найти наименьшее n, начиная с которого точность метода золотого сечения больше точности метода деления отрезка пополам в 2 раза, в 10 раз.

Упражнение 8. Написать алгоритм описанного метода.

Сравнение методов одномерной оптимизации показывает, что в большинстве случаев для гладких hello_html_278687bc.gif метод квадратичной интерполяции дает заметный выигрыш во времени. При сложныхhello_html_278687bc.gif метод золотого сечения может давать существенный выигрыш во времени. Метод квадратичной интерполяции удобен тем, что обнаруживает как максимумы, так и минимумы hello_html_278687bc.gif, причем даже за пределами первоначально заданного интервала поиска.

Численные методы поиска экстремумов функций многих переменных

Наибольшие трудности поиска минимума функции hello_html_me621af0.gifвозникают, когда размерность n вектора x велика. Поэтому важнейшей является проблема уменьшения размерности вектора минимизируемой функции на этапе построения математической модели решаемой задачи. В модели следует сохранить только те переменные hello_html_7a9f0571.gif, которые сильнее других влияют на изменение рассматриваемой функции.

Метод координатного спуска

Идея всех методов спуска состоит в том, чтобы исходя из начального приближения - точки

hello_html_m383f95df.gifDn (Dn - область определения функции) перейти в следующую точку

hello_html_m22d4de04.gifD так, чтобы значение hello_html_m1a807530.gif уменьшилось, т.е. hello_html_m708a556c.gif.

Рассматриваем функцию hello_html_c804914.gifпри фиксированных значениях hello_html_m38fe0da6.gifкак функцию одной переменной hello_html_m7d400f82.gif. Находим одним из описанных выше методов hello_html_m53d4ecad.gifhello_html_4ed27066.gif. Значение hello_html_m7d400f82.gif доставляющий минимум обозначаем hello_html_m4975d1f5.gif. hello_html_534d1f5d.gifhello_html_c804914.gif

После нахождения точки минимума по координате hello_html_m7d400f82.gif переходим к нахождению минимума по координате hello_html_m143463e.gif от новой точки и так далее по всем оставшимся координатам.

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

Центральным звеном рассматриваемого алгоритма является поиск минимума функции одной переменной. Методы применимые к этому случаю рассмотрены выше.

Градиентный метод

Пусть функция hello_html_278687bc.gif непрерывно дифференцируема на hello_html_35045d59.gif, а hello_html_m64452da2.gifhello_html_1ebcfeaf.gif

В основе градиентного метода минимизации (максимизации) функций многих переменных лежит следующее замечательное свойство градиента: при hello_html_m5af87d23.gifнаправление наибыстрейшего возрастания функции hello_html_278687bc.gifв точке hello_html_m5547f17b.gifсовпадает с направлением градиента hello_html_63086ecb.gif, а направление наибыстрейшего убывания - с направлением антиградиента hello_html_m77a7edf6.gif.

Это метод, как и все итерационные методы, предполагает выбор начального приближения - некоторой точки hello_html_3fea5f90.gif. Общих правил выбора точки hello_html_3fea5f90.gifв градиентном методе, как, впрочем, и в других методах, к сожалению, нет. В тех случаях, когда из геометрических, физических или каких-либо других соображений может быть получена априорная информация об области расположения точки (или точек минимума), то начальное приближение стараются выбрать поближе к этой области.

Пусть hello_html_3fea5f90.gif выбрано. Тогда градиентный метод заключается в построении последовательности {hello_html_m2207c6e8.gif} по правилу hello_html_36db8096.gif, hello_html_m5d468a40.gif, hello_html_m4d191f3a.gif.

hello_html_m5fe61f70.gif- длина шага или просто шаг градиентного метода.

Если hello_html_m57216f73.gif, то шаг hello_html_m5fe61f70.gifможно выбрать так, чтобы hello_html_m7c9f2602.gifhello_html_4c99c9c6.gif. Если hello_html_m27d8f031.gif, то hello_html_m2207c6e8.gif- точка минимума функции hello_html_278687bc.gif. В этом случае итерационный процесс прекращается.

Существуют различные способы выбора величины hello_html_m5fe61f70.gifв градиентном методе. В зависимости от способа выбора hello_html_m5fe61f70.gifможно получить различные варианты градиентного метода.

На луче, направленном по антиградиенту, введем функцию одной переменной hello_html_1aad8628.gif, hello_html_m604e442.gifи определим hello_html_m5fe61f70.gif из условий hello_html_3045c0fb.gif.

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

hello_html_m1a79811e.gif, или hello_html_m24ce6a67.gif, или hello_html_mb933788.gif, где hello_html_784c2195.gif- заданные числа.

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

Для более детального знакомства с данной темой предлагается книга Ф. П. Васильева "Численные методы решения экстремальных задач".

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Постановка задачи. Графический метод

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

Пример 1 (транспортная задача)

На две товарные станции привезли по 30 комплектов мебели. Мебель необходимо развести по трем магазинам (по 20 комплектов в каждый). Известна стоимость перевозок с каждой станции в каждый магазин:


Магазин 1

Магазин 2

Магазин 3

Станция 1

7

5

8

Станция 2

3

9

6

Требуется составить оптимальный (с наименьшими затратами) план перевозок.

Математическая постановка задачи:

Пусть х1, х2,...,х6- количество комплектов, которые надо перевезти со станций в магазины. Учитывая ограничения, получим для xi0 систему:

hello_html_559f50f3.gif

Получили систему из четырех уравнений с шестью неизвестными, у которой бесконечно много решений. Среди них надо выбрать такое, на котором целевая функция: f=7х1 + 3х2 + 5х3 + 9х4 + 8х5 + 6х6 достигает минимума.

Пример 2 (расчет рациона)

Имеются две питательные смеси, про которые известно, сколько белков, жиров и углеводов содержит одна единица каждой из них:


Жиры

Белки

Углеводы

Цена

1-я смесь

22

15

7

7

2-я смесь

16

11

9

6

Каждая корова должна получать не меньше 200 единиц жиров, 130 единиц белков и 75 единиц углеводов. Требуется подешевле накормить коров с учетом этих данных.

Математическая постановка задачи:

Пусть надо дать корове 1-ой смеси х1 единиц, 2-ой смеси- х2 единиц. Тогда

hello_html_mc151ed0.gif

Среди решений данной системы надо выбрать такое, на котором достигается минимум целевой функции f=7x1+6x2.

Пример 3 (распределение ресурсов)

Предприятие производит два вида продукции из двух видов сырья, причем известны запасы обоих видов сырья, расход сырья на каждый вид продукции и доход с одной единицы каждой продукции:


Сырье 1

Сырье 2

Доход

1-я продукция

15

20

70

2-я продукция

15

10

50

Запасы сырья

90

80



Требуется получить максимальную прибыль.

Математическая постановка задачи:

Обозначим через х1 и х2 планируемый выпуск первой и второй продукции. Тогда система ограничений будет иметь вид:

hello_html_m24201582.gif

Среди решений данной системы требуется найти такое, на котором достигается максимум целевой функции f=70x1+50x2.

Сходство математической постановки всех трех задач в том, что имеется целевая функция, у которой надо найти максимум или минимум, имеется система ограничений. При этом как ограничения, так и целевая функция являются линейными. Кроме того, во всех задачах есть требование неотрицательности переменных величин xi. Поскольку методы математического анализа для поиска экстремумов функций нескольких переменных для линейных функций не работают, то была создана теория линейного программирования, ориентированная на данный класс задач.

Задача линейного программирования в общем виде:

Дана система ограничений: АХ В, X 0, где А - матрица, Х и В - столбцы (возможно, разной длины). Дана линейная целевая функция: f = (с, х). Требуется определить компоненты вектора X, удовлетворяющие системе ограничений, при которых данная целевая функция принимает минимальное значение.

Определения. Решение называется допустимым в задаче линейного программирования, если оно удовлетворяет условиям: АХ В, Х 0.

Если существует хоть одно допустимое решение, то задача называется допустимой.

Вектор Х, который дает минимум целевой функции среди всех допустимых решений, называется оптимальным решением.

Если существует оптимальное решение, то говорят, что задача поставлена корректно.

Если в примере 2 умножить систему ограничений на -1, то вместо системы ограничений АХ В получим АХ В, т.е. получим задачу в общем виде.

В примере 1 вместо АХ В имеем АХ = В. Это частный случай.

В примере 3 вместо f = 70х1 + 50х2 -> max ищем f1 = -70х1 - 50х2 -> min.

(но не надо забывать в ответе поменять знак!)

Любую задачу линейного программирования можно свести к КАНОНИЧЕСКОМУ ВИДУ:

АХ = В, Х 0, f = (с, х) -> min.

Но при решении задачи нельзя механически заменять знак неравенства на знак равенства, т.к. после этого система, скорее всего, не будет иметь решения.

В задачах нет ограничения на количество неизвестных. За счет введения дополнительных неизвестных исходную систему неравенств легко свести к эквивалентной ей системе уравнений.

Например, задачу 3 можно так свести к канонической форме:

hello_html_m24201582.gif hello_html_m2a37b443.gif

f = 70х1 + 50х2 -> max f1 = -70х1 - 50х2 -> min


А в примере 2 достаточно провести следующие преобразования:

hello_html_m62ddf633.gif и f = 7х1 + 6х2 -> min

Решим эти задачи двумя способами: пример 1- аналитически, пример 3- графически.

В задаче 1 имеем 4 уравнения и 6 неизвестных, т.е. 2 степени свободы. Чтобы описать пространство решений, надо выбрать 2 независимые (свободные) переменные и через них выразить остальные переменные. Например, в качестве СВОБОДНЫХ возьмем х1 и х4. Неизвестные х2, х3, х5, х6 называются БАЗИСНЫМИ. Выразим их через свободные переменные и подставим все в целевую функцию:

х2= 20 -х1; х3= 20 – х4; х5= 10 - х1 + х4; х6= 10 + х1 – х4;

f = 7х1 + 3(20 - х1) + 5(20-х4) + 9х4 + 8(10 - х1 +х4) + 6(10+ х1 – х4) = 300 + 2х1 + 6х4.

Таким образом, мы нашли общее решение системы уравнений. При этом х1 и х4- свободные переменные, они могут принимать любые неотрицательные значения. Среди всех решений надо выбрать оптимальное. Т.к. f =300 + 2х1 + 6х3, и должно быть хi0, то ясно, что в оптимальном решении х1=0,х4=0. Тогда х2 = 20, х3 =20, х5 = 10, х6 = 10, f=300.

Графический метод решения задачи линейного программирования.

Решим ГРАФИЧЕСКИМ СПОСОБОМ пример 3. Его удобно применять, когда в задаче 2 (реже 3) неизвестных. В этом случае сначала строим область допустимых решений и в результате получаем многоугольник (многогранник). Затем можно действовать двумя способами. Во-первых, можно найти значения целевой функции в каждой из вершин и выбрать наименьшее. Во-вторых, можно нарисовать линии уровня целевой функции (это будут параллельные прямые) и с помощью них определить нужную нам вершину.


hello_html_m24201582.gif или hello_html_3a7a13e5.gif

Надо найти точку, в которой целевая функция имеет максимум. Для этого необходимо начертить график функции f = 0, т.е. 7х1 + 5х2 = 0 и сдвигать его параллельно в сторону увеличения функции f до тех пор, пока он все еще будет пересекать наш многоугольник (пересекаться с областью решений). Итак, самое оптимальное решение - точка (2;4), f = 340.

Двойственная задача

В матричном виде задача, двойственная к задаче линейного программирования в общем виде, имеет вид: АtY C, Y 0, V=(b,y) -> max.

Если взять двойственную задачу к двойственной, то получим исходную задачу. (Здесь Аt - транспонированная матрица).

ТЕОРЕМА. Задача линейного программирования корректна тогда и только тогда, когда исходная и двойственная задачи являются допустимыми. При этом минимум целевой функции в исходной задаче равен максимуму целевой функции в задаче двойственной.

Эта теорема позволяет вместо корректности задачи проверять два раза допустимость, что бывает заметно проще. Кроме того, важно, что ответы в двойственных задачах совпадают. Изредка, например когда имеем два неравенства со многими неизвестными, данная теорема позволяет перейти к случаю двух переменных и решать задачу графическим способом.

Напишем к задаче 2 двойственную:


hello_html_3253b7a1.gif, поэтому двойственная задача имеет вид: hello_html_62b50005.gif

и в ней ищется максимум функции V = 200y1 + 130y2 + 75y3

Упражнение: написать двойственную задачу к задаче 3.

СИМПЛЕКС - МЕТОД

Будем исследовать задачу линейного программирования в КАНОНИЧЕСКОЙ ФОРМЕ:

АХ = В, Х 0, f = (с, х) -> min.

При этом пусть A - матрица размером r*n, где r - число независимых уравнений, n-число переменных, r

Заданная система имеет бесконечно много решений, при этом множество решений системы образует пространство размерности n-r. Чтобы его описать, надо выбрать n-r свободных переменных, тогда оставшиеся r переменных будут называться базисными и выражаться через свободные переменные.

Договоримся, что свободные переменные имеют номера с r+1 до n-ого, т.е. базисными переменными являются x1,...,xr.

Вhello_html_28e90be2.gif
ыразив базисные переменные через свободные, линейную систему сведем к виду:

Если свободным переменным придать значение, равное 0, то получим решение: (b1,b2,...,br,0,0,...,0).

В каком случае этот набор будет допустимым решением задачи? Так как хi должны быть неотрицательными, то и все bi должны быть неотрицательными. Такое решение задачи называется базисным решением. Базисных решений много. Геометрический смысл базисного решения состоит в том, что это координаты одной из вершин многогранника допустимых значений в n-мерном пространстве. Если задача корректна, то одно из базисных решений задачи будет оптимальным. Следовательно, перебирая все вершины и вычисляя значение целевой функции в каждой из них, мы можем найти решение задачи. Однако, данный процесс очень трудоемок: для нахождения одного базисного решения придется решать систему уравнений r*n (а количество базисных решений равно числу сочетаний из n по r, т.е. весьма велико).

Симплекс-метод служит для облегчения процесса перебора: он заключается в последовательном переборе части базисных решений. Перебираются не все решения подряд, а только такие, что на каждом последующем шаге значение целевой функции становится лучше.

Описание симплекс-метода.

Выразим целевую функцию через свободные переменные и допишем к задаче:

f = 0 -r+1хr+1 - ... -nхn.

Для базисного решения получим f =0.

Перед нами стоит цель: уменьшить значение функции f за счет изменения свободных переменных. Свободные переменные для базисного решения равны 0, следовательно, мы можем их только увеличивать. Попробуем увеличивать хj, где r+1 j n. Можем ли мы за счет увеличения этой свободной переменной уменьшить значение целевой функции? Если j, положительное, то f уменьшается, а если j отрицательное или 0, то нет. Т.е. если j отрицательное, то нет смысла увеличивать хj, и наоборот.

Итак, если все j отрицательны, то данное базисное решение является оптимальным, а минимум целевой функции f равен 0.

Как перейти от одного базисного решения к другому, более хорошему? Пусть есть такое j, что j >0. При этом можно улучшить целевую функцию за счет увеличения хj. Все остальные свободные переменные оставляем равными 0. Тогда имеем:

hello_html_m403758e6.gif

Посмотрим, до какой степени можно увеличивать хj. Для этого надо определить, что происходит при этом с базисными переменными. Если коэффициент аij не положителен, то значение xi при увеличении xj тоже растет и это не препятствует неограниченному росту xj.

Если получилось, что в выбранном столбце все aij<=0, то задача поставлена некорректно, а оптимального решения не существует, поскольку можно бесконечно увеличивать х(j) и вместе с ним бесконечно уменьшать значение целевой функции, а решение все время будет оставаться допустимым.

Пусть среди аij есть положительные числа. Тогда при возрастании хj будут уменьшаться соответствующие базисные переменные xi. При этом увеличивать хj можно до тех пор, пока первая из переменных х1, х2...,хr обратится в 0. Это произойдет, когда хj примет значение минимальной из величин bii,j, у которых aij>0. После этого значение переменной хj станет отлично от 0,а какая-то из переменных хi обратится в 0. Это означает, что на очередном шаге мы переменную хj переводим в базисные, а хi - в свободные.

Алгоритм симплекс-метода:

1. Заполняем исходную таблицу (считается, что исходный базис найден).

2. Ищем в нижней строке максимальный положительный элемент (кроме 0). Если таких нет, то задача решена. Пусть j - максимальное положительное число в нижней строчке.

3. В j-том столбце ищем положительные коэффициенты аkj (если таких нет, то задача не имеет решения). Во вспомогательный столбец заносим bkkj. Пусть минимальный элемент во вспомогательном столбце находится в i-й строке. На пересечении разрешающего столбца (j) и разрешающей строки (i) находится разрешающий элемент aij.

4. Заполняем новую таблицу в следующем порядке:

  1. заголовок;

  2. первый столбец (вместо хi пишем хj);

  3. единичные столбцы;

  4. разрешающую строку (делим на аij);

  5. остальные строчки по порядку.

5. Возвращаемся к пункту 2.

hello_html_m5fda6a43.gif
ОСНОВНАЯ ФОРМУЛА симплекс-преобразования: (пункт 4) имеет вид:

Пример.

Решим с помощью симплекс-метода задачу:

hello_html_e5c343b.gif

Видно, что данная система решена относительно свободных переменных х4 и х5 и свободных при базисных переменных х1, х2 и х3. Заполняем исходную симплекс-таблицу и действуем далее по алгоритму.


Базис

Свободные члены

х1

х2

х3

х4

х5

Вспомогательный столбец

х1

2

1

0

0

-1

1

2 <- минимум

х2

7

0

1

0

2

3

7/3

х3

1

0

0

1

1

-2


f

3

0

0

0

-1

2


Базисное решение (2,7,1,0,0) f=3


Базис

Свободные члены

х1

х2

х3

х4

х5

Вспомогательный столбец

х5

2

1

0

0

-1

1


х2

1

-3

1

0

5

0

0.2 <- минимум

х3

5

2

0

1

-1

0


f

-1

-2

0

0

1

0


Базисное решение (0,1,5,0,2) f= -1


Базис

Свободные члены

х1

х2

х3

х4

х5

Вспомогательный столбец

х5

2.2

0.4

0.2

0

0

1


х4

0.2

-0.6

0.2

0

1

0


х3

5.2

1.4

0.2

1

0

0


f

-1.2

-1.4

-0.2

0

0

0


Базисное решение (0,0,5.2,0.2,2.2) f= -1.2

Видим, что данная таблица является последней и соответствующее ей базисное решение является оптимальным. Ответ получаем такой: fmin =-1.2, вектор X=(0;0;5.2;0.2;2.2).


Элементы математической статистики

hello_html_m53d4ecad.gifПроцесс познания окружающего нас мира включает наблюдение и эксперимент. Результаты наблюдений во многих случаях можно представить последовательностью действительных чисел hello_html_m5a2a9d2e.gif.

Для того, чтобы из ряда наблюдений можно было извлечь полезную информацию, необходимо иметь модель явления. Вероятностные модели оказываются наиболее пригодными при анализе явлений, исходы hello_html_m10d6c1e8.gifкоторых обладают некоторой степенью неопределенности. Понятие неопределенности в теории вероятностей формализуется путем введения распределения вероятностей на множестве hello_html_7ba38183.gif. В простейшем случае, когда hello_html_7ba38183.gifконечное или счетное множество, задаются вероятности hello_html_m264615fd.gifвсех его элементов hello_html_m5547f17b.gif, так что hello_html_37034035.gifи hello_html_m5ab73af.gif.hello_html_m53d4ecad.gif

Любое множество hello_html_mf66daa3.gifназывают в этом случае событием, а его вероятность определяют формулой hello_html_ma6011c2.gif.

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

Генеральная совокупность. Выборка. Статистические ряды

Пусть задача состоит в том, чтобы исследовать заданный качественный или количественный признак, характеризующий элементы некоторой последовательности (совокупности) наблюдений. Все множество объектов, входящих в рассматриваемую совокупность называют генеральной совокупностью. Число элементов генеральной совокупности может быть достаточно большим (в теоретических рассмотрениях используется и совокупности, содержащие бесконечное множество элементов).

Часть генеральной совокупности, выбранную из нее некоторым (случайным) образом, называют выборочной совокупностью (выборкой). Объем выборки, обозначаемый hello_html_m601acf03.gif(по количеству элементов), может быть и сравнительно большим и малым, но не может содержать меньше двух единиц. Выборочный метод является основным при изучении статистических совокупностей. Его преимущество перед сплошным учетом всех членов генеральной совокупности заключается в том, что он сокращает время и затраты труда (за счет уменьшения числа наблюдений), а главное позволяет получать информацию о таких совокупностях, сплошное исследование которых практически невозможно или нецелесообразно.

Элементы совокупности называют вариантами. Существует два основных способа отбора вариант из генеральной совокупности: повторный и бесповторный. В практике обычно применяют бесповторный отбор.

Статистическими рядами называют ряды числовых значений некоторого признака, расположенного в определенном порядке.

Расположим варианты hello_html_120f6006.gif (hello_html_m601acf03.gif- объем выборки) в порядке возрастания и перенумеруем их заново: hello_html_b381716.gif , где

hello_html_3144e276.gif, hello_html_m6461d511.gif.

Такую перенумерованную последовательность часто называют вариационным рядом.

Числа, показывающие сколько раз отдельные варианты встречаются в данной совокупности, называются частотами или весами вариант и обозначаются hello_html_2489d00d.gif или hello_html_m7f97fea9.gif.

Общая сумма частот всегда равна объему выборки. Говорят еще об относительных частотах (выражаются в частях или % от hello_html_m601acf03.gif).

Интервальный вариационный ряд, такой статистический ряд, в котором частоты распределяются по отдельным интервалам или промежуткам (от - до), на которые разбивается вариация признака в пределах от минимальной до максимальной варианты совокупности. Эти промежутки или классовые интервалы могут быть равными и неравными по ширине. Чаще всего рассматриваются равные интервалы. Величина равных интервалов определяется делением размаха варьирования признака (hello_html_55c50be3.gif) на число групп или классов (hello_html_3eb40b6c.gif), намечаемых при построении вариационного ряда:

hello_html_m4fdcb5f9.gif , где hello_html_52908ad7.gif- величина классового интервала, а величина hello_html_3eb40b6c.gifопределяется по формуле Стерджеса hello_html_m8d94fb7.gif.

В общем случае техника построения вариационного ряда сводится к следующему:

  1. составляем сводку исходных данных;

  2. отыскиваем hello_html_m43f4758e.gifи hello_html_m109a26ae.gifварианты;

  3. определяем величину классового интервала hello_html_52908ad7.gifпо формуле данной выше. Если значения признака выражены целыми числами и классовый интервал hello_html_52908ad7.gifокажется равным 1 (или 1), выборка распределяется в безинтервальный вариационный ряд. Если hello_html_52908ad7.gif1, выборку следует распределять в интервальный вариационный ряд. Кроме того, следует соблюдать правило, согласно которому величина классового интервала должна соответствовать точности, принятой при измерении учитываемого признака (если =0,001 , то классовый интервал тоже определяется с точностью 0,001);

  4. при построении интервального вариационного ряда следует добиваться того, чтобы минимальная варианта hello_html_m43f4758e.gifпопадала в середину классового интервала, то есть, hello_html_192b8e0f.gif, где hello_html_mb0d45d7.gif- нижняя граница первого классового интервала. Определяем верхнюю границу первого классового интервала hello_html_m5be08723.gif, второго классового интервала hello_html_m7df33604.gif, hello_html_3eb40b6c.gif- того классового интервала hello_html_m3ffb8bf6.gif.

  5. наметив классовые интервалы, остается распределить по ним варианты выборки, то есть, определить частоты каждого класса.


Графическое изображение вариационных рядов. Эмпирическое распределение

При построении графика зависимости частот от значений вариант безинтервального вариационного ряда по оси абцисс откладываются значения классов (вариант) по оси ординат - частоты. В результате будет построена геометрическая фигура в виде многоугольника. Полученный график называют полигоном распределения частот.

При построении графика зависимости частот от значений вариант интервального вариацинного ряда по оси абцисс откладывают границы классовых интервалов, по оси ординат - частоты. В результате - гистограмма распределения частот. Можно поступить иначе: по оси абцисс отложить срединные значения классов (hello_html_m704f9935.gif), по оси ординат частоты для указанного класса.

Вариационная кривая - это сглаженные значения полигона.

Совокупность значений hello_html_7a9f0571.gif и соответствующих им частот называется эмпирическим распределением.

Средние величины и показатели вариации

Вариационные ряды и их графики дают наглядное представление о том, как варьирует тот или иной количественный признак. Но они недостаточны для полной характеристики статистической совокупности. Количественные показатели, которые (логически и теоретически обоснованы) позволяют судить о качественном своеобразии варьирующих объектов и сравнивать их между собой, называются статистическими характеристиками.

В отличие от индивидуальных числовых характеристик средние величины обладают большей устойчивостью, способностью характеризовать группу однородных вариант одним (средним) значением. И хотя средние абстрагируют нас от конкретных вещей, они вполне понятны и ощутимы. Средний рост, средняя масса …(то есть, здесь уравновешиваются все индивидуальные отклонения и появляется качественное своеобразие группового объекта).

По определению Гаусса, истинной средней служит такая величина, сумма квадратов отклонений от которой обладает нименьшим значением.

hello_html_3ee39b3e.gif , где hello_html_465b1232.gif - средняя величина, hello_html_7a9f0571.gif- варианта, hello_html_m601acf03.gif- объем выборки, hello_html_m5faf1d98.gif- величина, определяющая вид средней.

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

hello_html_m28138aa0.gif- средняя гармоническая. В этом случае hello_html_e0d9355.gif. В некоторых случаях для усреднения количественных признаков используется такой тип средней.

hello_html_m69872f02.gif- средняя квадратическая. При выражении количественных признаков вариант мерами площади более точной усредненной характеристикой будет средняя квадратическая hello_html_m1160093f.gif.

hello_html_1af8a31c.gif- средняя кубическая. Более точная средняя характеристика, в тех случаях, когда варьирующий признак выражен в объмных единицах.

hello_html_66806368.gif.

Средняя геометрическая является более точной характеристикой при определении средних прибавок или при увеличении линейных размеров тел, прироста численности популяции за определенный промежуток времени.

hello_html_m7abdcdfd.gif .

hello_html_7e74c189.gif- средняя арифметическая. Эту величину рассмотрим подробнее.

Средняя арифметическая и ее свойства

hello_html_627420d4.gif- средняя арифметическая является центром распределения, вокруг которого группируются все варианты статистической совокупности.

hello_html_m53d4ecad.gifhello_html_m53d4ecad.gifhello_html_m1e006148.gif.

Если рассматривается интервальный вариационный ряд, то средняя арифметическая, называемая взвешенной, вычисляется по формуле

hello_html_12b21060.gif , где hello_html_a3573a4.gif- частота hello_html_52908ad7.gif- ого класса, hello_html_346fed48.gif, hello_html_3eb40b6c.gif- количество классовых интервалов. Рассмотрим свойства средней арифметической.

Свойство 1. Если каждую варианту совокупности уменьшить или увеличить на какое-то произвольное положительное число А, то и средняя арифметическая уменьшится или увеличится на столько же.

Упражнение 1. Доказать свойство 1.

Свойство 2. Если каждую варианту разделить или умножить на одно и тоже число А, то и средняя арифметическая изменится во столько же раз.

Упражнение 2. Доказать свойство 2.

Свойство 3. Сумма произведений отклонений вариант от их средней арифметической на соответствующие им частоты равна нулю.

Упражнение 3. Доказать свойство 3.

Свойство 4. Сумма квадратов отклонений вариант от их средней арифметической меньше суммы квадратов отклонений тех же вариант от любой другой величины А, не равной средней арифметической.

Упражнение 4. Доказать свойство 4.

Размах вариации hello_html_55c50be3.gifхарактеризует варьирование признака в совокупности.

Рассмотрим еще две характеристики выборочной совокупности: дисперсию и среднее квадратическое отклонение. Эти величины характеризуют не только величину, но и специфику варьирования признака.

Дисперсия и ее свойства. Среднее квадратическое отклонение

Дисперсия (или варианта) - это средний квадрат отклонений вариант данной совокупности от их средней величины.

Дисперсия hello_html_1e34f0f3.gif или, если используется интервальный вариационный ряд

hello_html_563104a3.gif.

Свойства дисперсии

Свойство 1. Если каждую варианту совокупности уменьшить или увеличить на одно и тоже постоянное число А, то дисперсия не изменится.

Упражнение 4. Доказать свойство 1.

Свойство 2. Если каждую варианту разделить (или умножить) на одно и тоже постоянное число А, то дисперсия уменьшится (или увеличится в А2 раз.

Упражнение 2. Доказать свойство 2.

Среднее квадратическое отклонение определяется по следующей формуле:

hello_html_m60d4680c.gif. Чем сильнее варьирует признак, тем больше величина этого показателя и наоборот.

Коэффициент вариации

Дисперсия и среднее квадратическое отклонение - величины абсолютные и имеют размерность вариант совокупности. Если же хотим сравнивать изменчивость признаков, выраженных разными единицами, следует перейти к относительным показателям.

Один из этих показателей - показатель Пирсона (коэффициент вариации)

hello_html_6b36c915.gif .

Чем выше %, тем более изменчив признак.

Структурные средние

Медиана (hello_html_371447f1.gif) эмпирического распределения - средняя, относительно которой ряд распределения делится на две половины: в обе стороны от медианы располагается определенное число вариант. Если число вариант нечетно - центральная варианта его медиана. При четном - определяется по полусумме соседних вариант, расположенных в центре ряда.

Мода (hello_html_4e5295f3.gif) - величина, которая встречается в данной совокупности наиболее часто. Класс с наибольшей частотой называется модальным.

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

Законы распределения случайных величин

Между отдельными значениями варьирующих признаков и частотой их встречаемости в генеральной совокупности существует определенная связь (это наглядно можно увидеть на графике зависимости частот от значения вариат).

Реализация того или иного эначения варьирующего признака представляет собой случайное событие. Предсказать появление случайного события в отдельных испытаниях (наблюдениях) можно лишь с некоторой уверенностью, или вероятностью, которое имеет данное событие. Случайной называется переменная величина, способная в одних и тех же условиях испытания принимать различные числовые значения. Функция hello_html_m4c79cead.gif, связывающая значения вариант hello_html_7a9f0571.gifс вероятностями hello_html_m2e93142c.gifназывается законом распределения случайной величины.

В природе широко распространена закономерность: в массе относительно однородных членов, составляющих статистическую совокупность, большинство их оказывается среднего или близкого к нему размера, и чем дальше они отстоят от среднего уровня варьирующего признака , тем реже встречаются в данной совокупности. Такое поведение может описано законом нормального распределения (формула Гаусса-Лапласа)

hello_html_345147d5.gif , где hello_html_1381e5bb.gif- дисперсия генеральной совокупности, hello_html_m77b294c2.gif- генеральная средняя арифметическая или математическое ожидание.

Величина hello_html_m6179756c.gif получила название нормированного отклонения.

Выборочные характеристики рассматриваются как приближенные значения или точечные оценки соответствующих генеральных параметров, которые, как правило, остаются неизвестными. Средняя арифметическая выборки hello_html_627420d4.gifслужит оценкой средней арифметической генеральной совокупности hello_html_m77b294c2.gif, выборочная дисперсия hello_html_4e617700.gif является оценкой генеральной дисперсии hello_html_1d660d6a.gif, hello_html_10784440.gif - в качестве точечной оценки стандартного отклонения hello_html_3660d034.gifгенеральной совокупности.

Формально математическое ожидание соответствует средней арифметической эмпирических распределений. Однако отождествлять эти величины нельзя. Средняя арифметическая выражается отношением суммы всех членов ряда к их общему числу, а математическое ожидание представляет сумму произведений членов ряда на их вероятности. Эмпирическая средняя стремится к своей вероятной величине, то есть, к математическому ожиданию по мере увеличения числа испытаний: чем больше число испытаний, тем ближе эмпирическая средняя к математическому ожиданию.

Статистические гипотезы

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

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

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

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

Противоположная или альтернативная гипотезаhello_html_m35d00ae7.gif, наоборот, исходит из предположения, что между генеральными параметрами сравниваемых групп разница не равна нулю.Статистические гипотезы могут исходить и из других предположений.

Истинность принятой гипотезы проверяется с помощью критериев значимости, или достоверности, то есть, специально выработанных случайных величин, функции распределения которых известны. Обычно для каждого критерия составляется таблица, в которой содержатся критические точки, отвечающие определенным числам степеней свободы (hello_html_m5faf1d98.gif) и принятым уровням значимости hello_html_284e617c.gif.

Уровни значимости - значение вероятности, при котором различия, наблюдаемые между выборочными показателями, можно считать несущественными, случайными. В исследовательской работе обычно принимается 5% уровень значимости, который соответствует вероятности hello_html_777fe0b1.gif=0,05 и нормированное отклонение hello_html_m54bac51.gif, если распределение критерия нормально. Если окажется, что hello_html_m1475eb33.gif, то нулевая гипотеза сохраняется, иначе отвергается.

Рассмотрим гипотезу о равенстве средних арифметических исходных генеральных совокупностей. В рассмотрении участвуют две выборки и их параметры: объем выборки и средняя арифметическая (hello_html_17aa43f7.gifиhello_html_627420d4.gif для первой выборки и hello_html_m601acf03.gifи hello_html_1468bd41.gifдля второй). Нулевая гипотеза предполагает, что hello_html_m27d7f6ec.gif.

Имеется ли различие между этими средними значениями? Чтобы определить какой характер носит это различие используют критерий Стьюдента. Вычисленное значение критерия будет определено по формуле:hello_html_m78ee574d.gif , а hello_html_m10d53474.gif.

Вычисленное значение критерия сравниваем с критической точкой, взятой из таблицы распределения Стьюдента в соответствии с выбранным уровнем значимости и числом степеней свободы hello_html_7847294e.gif. Если hello_html_46bb81af.gif больше табличного значения, то гипотезу о равенстве средних следует отвергнуть. Это будет означать, что различие средних нельзя считать случайным.

Теперь рассмотрим гипотезу о равенстве дисперсий исходных генеральных совокупностей. В рассмотрении участвуют две выборки и их параметры: объем выборки и дисперсия (hello_html_17aa43f7.gifиhello_html_4e617700.gif для первой выборки и hello_html_m601acf03.gifи hello_html_b01445b.gifдля второй). Нулевая гипотеза предполагает, что hello_html_105388ba.gif. Воспользуемся критерием Фишера hello_html_53cbd563.gif(отношение большей из дисперсий к меньшей). Вычисленное значение критерия Фишера сравниваем с критическим значением, взятым из таблицы распределения Фишера в соответствии с уровнем значимости hello_html_284e617c.gifи степенями свободы hello_html_17aa43f7.gifиhello_html_m601acf03.gif. Если вычисленное значение критерия больше табличного, то различие выборочных дисперсий следует признать значимым.

Чтобы проверить, распределен ли варьирующий признак по нормальному закону, поступают следующим образом. Пусть элементы выборки распределены по hello_html_3eb40b6c.gif- интервалам, причем hello_html_680c16df.gif- тому интервалу (hello_html_2f9b596e.gif) соответствуе частота hello_html_3154f8f0.gif. Для проверки гипотезы о каком - либо распределении случайной величины используют критерий hello_html_458cb2c7.gif(критерий Пирсона).

Вычисленное значение критерия определяется по формуле: hello_html_60be9305.gif, где hello_html_3154f8f0.gif- относительная частота соответствующая hello_html_680c16df.gif- ому интервалу, hello_html_2650e201.gif- теоретическая частота, соответствующая hello_html_680c16df.gif- ому интервалу. Правило вычисления hello_html_2650e201.gifи определение числа степеней свободы зависит от вида теоретического распределния и способа оценки его параметров.

Сравним эмпирическое распределение с нормальным.

hello_html_19e18e10.gif, где hello_html_9d1390c.gifи hello_html_7c7277a3.gif- левая и правая границы hello_html_680c16df.gif- ого интервала, hello_html_358b6473.gif- плотность нормального распределения. Для упрощения вычислений можно заменить интеграл в правой части этого равенства произведением длины промежутка интегрирования и значения функции в средней точке интервала, то есть, hello_html_3542db22.gif.

В таблице распределения hello_html_458cb2c7.gifнаходим критическую точку, соответствующую выбранному уровню значимости hello_html_284e617c.gifи числу степеней свободы hello_html_m30a4612b.gif (если hello_html_m77b294c2.gifи hello_html_7691e7c8.gifне определяются по имеющимся данным, а известны заранее, то число степеней свободы hello_html_m39d5086.gif). Если вычисленное по формуле значение критерия больше табличного, то на уровне значимости hello_html_284e617c.gifпрверяемая гипотеза должна быть отвергнута.

Можно поступить еще и так. Пусть hello_html_3154f8f0.gif- абсолюное значение частоты hello_html_680c16df.gif- ого интервала. Можно сравнить частоты теоретические и эмпирические. В этом случае hello_html_3ac4b986.gif , где hello_html_m601acf03.gif- объем выборки.

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

Кривую нормального распределения характеризуют величины асимметрия (hello_html_m36e3b872.gif) и эксцесс.(hello_html_62f295b5.gif). Эти величины для рассматриваемой выборки можно определить, зная выборочные характеристики: среднюю арифметическую и дисперсию.

hello_html_2891429c.gif , hello_html_m5136c1d3.gif.

Можно оценить статистические ошибки выборочных характеристик. Для выборочной средней hello_html_m2ac13f3e.gif, для асимметрии hello_html_68400db8.gif, для эксцесса hello_html_m3da62069.gif. И нулевая гипотеза о том, что эмпирическое распределение нормально будет отвергаться, если hello_html_7c09f58d.gifи hello_html_5ebb42c0.gif.

Литература

  1. Боглаев Ю. П. Вычислительная математика и программирование. - М.: - Высшая школа, 1990.

  2. Васильев Ф. П. Численные методы решения экстремальных задач. - М.: - Наука, 1988.

  3. Власов В. К., Королев Л. Н., Сотников А. Н. Элементы информатики. - М.: - Наука, 1988.

  4. Воробьева Г. И., Данилова А.Н. Практикум по вычислительной математике. - М.: - Высшая школа, 1990.

  5. Дьяконов В.П. Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ. - М.: - Наука, 1987.

  6. Иванова Т. П., Пухова Г. В. Программирование и вычислительная математика. - М.: - Просвещение, 1998.

  7. Кимбл Г. Как правильно пользоваться статистикой. - М.: - Финансы и статистика, 1982.

  8. Козлов М. В., Прохоров А. В. Введение в математическую статистику. - М.: - Издательство МГУ, 1987.

  9. Кузнецов Ю. Н., Кузубов В. И., Волощенко А.Б. Математическое программирование. - М.: - Высшая школа, 1976.

  10. Севастьянов Б. А. Курс теории вероятностей и математической статистики. - М.: - Наука, 1982.



Численные методы: теория и практика
  • Математика
Описание:

Одна из самых больших проблем преподавателей математики в колледже состоит в том, что по дисциплине "Численные методы" практически нет ни учебников, ни пособий.

Вот и я в своё время стояла перед проблемой: предмет вести необходимо, а нет ни учебников, ни пособий. Что же делать? 

Ответ был прост: искать любую, доступную информацию. Всё систематизировать и привести к виду, несущему максимум информации. 

Результат моих поисков - перед Вами.

Данный сборник содержит теоретический материал по всем изучаемым методам.

Разработаный материал носит информационный, рекомендательный жарактер

Автор Матушевич Лариса Викторовна
Дата добавления 20.12.2014
Раздел Математика
Подраздел
Просмотров 1804
Номер материала 8945
Скачать свидетельство о публикации

Оставьте свой комментарий:

Введите символы, которые изображены на картинке:

Получить новый код
* Обязательные для заполнения.


Комментарии:

↓ Показать еще коментарии ↓