Материал: Пособие с Алгоритмами

3. Алгоритм аппроксимации функции методом наименьших квадратов

Схема алгоритма, аппроксимации функции по методу наименьших квадратов (МНК) приведена на рис. 2.4-1.

МНК[3] является одним из наиболее распространенных методов аппроксимации функции. В этом методе параметры a₀, a₁, ..., a_n определяются из условия минимума суммы квадратов отклонений значений аппроксимирующей функции от табличных данных.

Вектор коэффициентов a^T определяют из условия минимизации

где (n+1) – количество узловых точек.

φ(x)=a₀φ₀(x)+a₁φ₁(x)+...+a_mφ_m(x) – аппроксимирующая функция степениm

Для получения искомых значений параметров a₀, a₁,…a_mследует составить и решить систему (m+1) линейных уравнений

В качестве меры уклонения заданных значений функции y₀, y₁, ..., y_n от многочлена степени m -, принимается величина

Поскольку МНК требует решения системы линейных уравнений (СЛУ), на рис. 2.4-2 приведена схема алгоритма решения СЛУ методом Гаусса [1]. Метод сводится к последовательному исключению из всех уравнений, начиная со второго, затем - начиная с третьего и т.д. Это позволяет получить эквивалентную систему, имеющую треугольную матрицу (прямой ход), а затем, действуя в противоположной последовательности, получают решение (обратный ход).

Рис. 2.3-1.Алгоритм метода наименьших квадратов

Рис. 2.3-2. Формирование матрицы Грама

Рис. 2.3-3. Вычисление элемента матрицы Грама

Рис. 2.3-4. Вычисление элемента правой части системы нормальных уравнений

Рис. 2.3-5.Решение системы линейных уравнений методом Гаусса

Рис. 2.3-6.Вычисление значения аппроксимирующей функции в заданных точках

Рис. 2.3-7. Вычисление невязки

4. Алгоритмы методов численного интегрирования

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

Во всех алгоритмах оценка погрешности проводится с использованием метода двойного просчета [3], который основан на двукратном вычислении значения интеграла вначале с шагом h(где h=(b-a)/n), а затем с шагом h/2. Значения интегралов I_hи I_h/2 могут быть применены для оценки погрешности интегрирования по формуле Рунге:

где: k - порядок точности метода.

1. Метод средних прямоугольников

Схема алгоритма процедуры для вычисления определенного интеграла методом средних прямоугольников представлена на рис. 2.4-1. Эта схема требует дополнения процедуры-функции f(x), в которой вычисляется значение подынтегральной функции.

Алгоритм метода основан на замене подынтегральной функции f(x) в пределах элементарного отрезка [x_i;x_i+1] интерполяционным многочленом нулевой степени, равным значению функции в середине отрезка [3]. Вычисление интеграла проводится с использованием формулы:

Оценка погрешности проводится с использованием метода двойного просчета, где в формуле Рунге k=2.

Рис. 2.4-1. Метод средних прямоугольников

2. Метод трапеций

Алгоритм метода трапеций, представленный на рис. 2.4-2, должен быть дополнен процедурой-функцией f(x), в которой вычисляется значение подынтегральной функции.

Рис. 2.4-2. Алгоритм метода трапеций

Алгоритм метода основан на замене подынтегральной функции f(x) в пределах элементарного отрезка [x_i;x_i+1] интерполяционным многочленом первой степени[3]. Вычисление интеграла проводится с использованием формулы:

Оценка погрешности проводится с использованием метода двойного просчета, где формуле Рунге k=2.

3. Метод Симпсона

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

Рис. 2.4-3. Алгоритм метода Симпсона

Алгоритм метода Симпсона основан на замене подынтегральной функции f(x) в пределах двух элементарных отрезков [x_i;x_i+2] интерполяционным многочленом второй степени[3]. Количество отрезков должно быть четным (n=2m). Вычисление интеграла проводится с использованием формулы:

Оценка погрешности проводится с использованием метода двойного просчета, где формуле Рунге k=4.

5. Алгоритмы методов решения обыкновенных дифференциальных уравнений

Схема алгоритма решения обыкновенных дифференциальных уравнений (ОДУ) методами Рунге-Куттыс заданной точностью представлена на рис. 2.5-1.

Рис.2.5-1. Алгоритм решения ОДУ методами Рунге-Кутты

В зависимости от порядка метода схема алгоритма дополняется соответствующей процедурой, в которой производится вычисление функции y(x_i), по формулам соответствующим порядку метода Рунге-Кутты (рис.2.5-2).

Рис.2.5-2. Решение ОДУ методами Рунге-Кутты с постоянным шагом

Заданная погрешность обеспечивается дополнением алгоритмов решения методом двойного просчета, в котором оценка погрешности производится по формуле Рунге:

где p – порядок метода Рунге-Кутты.

Если условие выполняется, то шаг для следующей точки выбирается равным величине h, иначе шаг уменьшается вдвое и продолжается уточнение y_iв точке х_i.

6. Алгоритмы методов одномерной оптимизации

   1. Метод дихотомии

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

Рис.2.6-1. Алгоритм метода дихотомии

В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b][3].На отрезке [a₀;b₀], где a₀=a, аb₀ = b, выбираются две точки симметричные относительно середины отрезка:

где d - параметр метода, величина которого (0<d<e/2.).

Вычислим и сравним значения функций f(a₁) и f(b₁). В силу унимодальности функции можно провести сокращение отрезка неопределенности по следующему правилу:

Еслиf(a₁) £f(b₁), то x*Î[a₀;b₁] ;

Если f(a₁) >f(b₁), то x*Î[a₁;b₀].

Сокращение отрезка проводятся до тех пор, пока не выполнится неравенствоΔ_n=|b_n-a_n|≤ε.

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

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

Рис.2.6-2. Алгоритм метода золотого сечения

В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b] [3].В основу метода положено разбиение отрезка неопределенности [a;b] в соотношении золотого сечения:

или ,

где k₁=0.382, а k₂=0.618.

Сравнение значений функции в точках х₁ и х₂ позволяет, в силу унимодальности функции f(x), отбросить ту часть отрезка, где заведомо нет точки минимума. Известно, что и точка х₁и точка х₂дваждыосуществляет золотое сечение на отрезке[a;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Сокращение отрезка проводятся до тех пор, пока не выполнится неравенствоΔ_n=|b_n-a_n|≤ε.

3. Метод средней точки

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

Рис. 2.6-3. Алгоритм метода средней точки

Алгоритм метода средней точки [2] основан на сокращении длины текущего отрезка неопределенности [a;b], путем отбрасывания той половины отрезка, которая не содержит точки минимума. В основу метода положено основное свойство унимодальности функции, то есть, для того чтобы на отрезке [a;b] существовал минимум, необходимо, чтобы первая производная на нем была неубывающей. Выбрав середину текущего отрезка c=(a_i+b_i)/2), принимается решение: если , то в следствии унимодальности функции, точка минимума не может лежать левее точки с, переопределяется левая граница отрезка(a_i+1=с), а если , то минимум не может лежать правее точки с и переопределяется правая граница отрезка (b_i+1=c). В случае если за точку минимума принимают значение с.

Сокращение отрезка проводятся до тех пор, пока не выполнится неравенствоΔ_n=|b_n-a_n|≤ε.

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

7. Алгоритмы методов многомерной оптимизации

Итерационные методы, применяемые для решения задач минимизации функции нескольких переменных, относятся к классу методов спуска[3]. В них каждая итерация(k) приводит к уменьшению значения целевой функции: Q(x_k+1,y_k+1)<Q(x_k,y_k), для всех k³0.

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

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

где l_k - шаг спуска. Способ задания шага спуска l_k определяется конкретным методом.

Итерации повторяются до тех пор пока не выполняется условие окончания цикла:

Схема алгоритма метода градиентного спуска, представленная на рис. 2.7-1, требует дополнения следующих процедур-функций:

• Q(x,y) – целевая функции;

• g1(x,y) – частная производная по х;

• g2(x,y)– частная производная по y.