Численные методы (стр. 2 )

1) если С — постоянная, то ;

2) ;

3) ;

4) .

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

1.1.2. Интерполяционные формулы Ньютона[6]

Пусть задана таблица значения функции для равностоящих узлов :

Требуется построить полином степени не выше , удовлетворяющий условиям: , . Будем искать в виде

Используя условие можно найти все коэффициенты , ,…, . Эти коэффициенты выражаются через конечные разности.

Полагая , находим:

Следовательно .

Полагая , получаем:

,

откуда . Поскольку , то .

Полагая , получаем:

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

,

или , но , откуда

Полагая и проведя аналогичные выкладки, можно получить: .

В общем случае выражение для коэффициента будет иметь вид: .

Подставив найденные коэффициенты , , …, в выражение для многочлена , получим первую интерполяционную формулу Ньютона в виде:

Для практического использования эту формулу записывают по-другому. Введем . Тогда:

,

.

.

.

,

.

Таким образом, первую интерполяционную формулу Ньютона можно записать в виде:

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

, здесь .

1.2. Эмпирические формулы

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

1) заранее не задается вид аппроксимирующей функции как полином - й степени;

2) не требуется совпадения значений аппроксимирующей функции в узлах с табличными данными.

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

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

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

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

Пусть результаты анализа экономических данных представлены в виде таблицы дискретных значений и

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

Требуется найти эмпирическую формулу:

“наиболее хорошо” описывающую табличные данные.

Здесь , – параметры, число которых .

Эта задача разбивается на два этапа:

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

2)  определение “наилучших” параметров выбранной эмпирической формулы.

Рассмотрим каждый этап подробно.

1.2.2. Выбор вида эмпирической формулы

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

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

1.2.3. Метод наименьших квадратов для отыскания параметров эмпирической формулы

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

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

По МНК параметры подбираются так, чтобы сумма квадратов отклонений была минимальной:

.

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

.

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

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

Линейная зависимость имеет вид:, поэтому

и соответственно

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

Аналогично для квадратичной зависимости имеем:

и соответственно

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

1.2.4. Нахождение эмпирической формулы в виде некоторых элементарных функций

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

В качестве эмпирических формул, кроме линейной и квадратичной, часто используют следующие функции:

Здесь – параметры.

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

1. Степенная функция. Будем искать эмпирическую формулу в виде: .

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

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

1) по исходной таблице данных составить новую таблицу, прологарифмировав значения и в данной таблице;

2) по новой таблице, используя систему нормальных уравнений для линейной функции, найти параметры и ;

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

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

Прологарифмируем равенство : .

Обозначив, , получим: .

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

3. Дробно-линейная функция. Будем искать эмпирическую формулу в виде: .

Перепишем это равенство следующим образом: .

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

4. Логарифмическая функция. Пусть эмпирическая формула имеет вид: .

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

5. Гипербола. Если точечный график, построенный по данным таблицы, дает ветвь гиперболы, то эмпирическую формулу можно искать в виде: .

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

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

6. Дробно-рациональная функция. Пусть эмпирическая зависимость ищется в виде: .

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

Тема 2. Итерационные методы решения систем линейных уравнений

2.1. Введение

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

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

С увеличением порядка системы число операций (умножение, деление, сравнение, сложение, вычитание), необходимых для решения системы, быстро растет. Число операций, требуемых для решения, зависит не только от порядка системы, но и от метода решения. Поясним это примером. Предположим, что дана система n уравнений с n неизвестными и определителем, отличным от нуля. По известной из курса высшей математики теореме Крамера система имеет единственное решение. В этой теореме указывается явное выражение для значений неизвестных в виде отношения двух определителей порядка n, при этом число различных определителей в отношениях равно n + 1.

Пусть для нахождения решения мы хотим воспользоваться теоремой Крамера, при этом определители будем вычислять по их определению, как сумму со знаками плюс или минус произведений n! элементов по одному из каждой строки и каждого столбца. Для нахождения решения нужно будет порядка операций. Поскольку n! = n·(n – 1)·(n – 2)…3·2·1, то уже при n = 20 это число приближенно равно и является настолько большим, что становится ясной невозможность решать указанным путем на ЭВМ систему даже двадцати уравнений.