К разделу 'Математика' сайта AlgoList.

Назад Оглавление Вперед

Алгоритмы с конечной точностью

Разложения, аппроксимирующие заданную функцию с некоей априори фиксированной точностью, можно получать множеством самых разных способов. Для получения полиномиальных приближений, например, одним из самых простых и мощных является, на мой взгляд, принадлежащий Ланцошу [5] процесс экономизации степенных рядов. Некоторые способы получения рациональных приближений описаны в работах [3, 6]; список литературы, посвященной этой проблематике, легко может быть продолжен.

В данном параграфе я приведу несколько таких широко известных разложений [10]. Разложения получены с помощью «грубой силы»: фиксировав вид аппроксимации, по значениям функции в нескольких точках можно оценить значения констант. Точность полученной аппроксимации оценивается сравнением истинных значений F(xi) и аппроксимирующих F*(xi) во многих точках. Успех всего предприятия определяется, конечно, нашей удачливостью в выборе вида аппроксимации.

Вот, например, как можно получить разложение A2. Начнем с того, что фиксируем вид аппроксимации

(1) 

Перепишем (1) в более удобном виде

(2) 

и положим

(3) 

Вычислив y(x) в точках x0, x1, x2, x3, получаем четыре нелинейных уравнения для определения констант c0, c1, c2, c3, p:

(4) 

Полученная система уравнений совместна относительно неизвестных c0, c1, c2, c3 (константу p пока считаем известной) тогда и только тогда, когда детерминант

равен нулю. Разложив этот определитель по элементам правого столбца, получаем уравнение

(5) f(p) = A0(1+px0)3 + A1(1+px1)3 +

A2(1+px2)3 + A3(1+px3)3 = 0, в котором A0, A1, A2 и A3 известны. Для определения корней этого уравнения используется какая-нибудь стандартная процедура, например, метод Ньютона. В работе [10] описаны причины, по которым в качестве p следует выбирать наименьший действительный корень уравнения (5).

Отбрасывая теперь любое (например, последнее) уравнение в системе (4), получаем линейную систему

решив которую, получаем требуемые значения констант. Переход от разложения вида (2) к разложению A2 тривиален.

Алгоритмы, реализующие разложения A1-A4, приведены в приложении B; во всех этих алгоритмах для вычисления полинома использована схема Горнера.

A1: F(x) = 1-1/2(1 + a1x + a2x2 + a3x3 + a4x4)-4 + e(x),

|e(x)| < 2.5ґ10-4, 0 Ј x < z1 = 3.72

a1 = 0.196854, a3 = 0.000344,
a2 = 0.115194, a4 = 0.019527;
F(x) = 1 при x і z1.
A2: F(x) = 1- j(x) (b1t + b2t2 + b3t3) + e (x),
|e(x)| < 10-5, 0 Ј x < z2 = 4.27
b1 = 0.4361836, b2 = -0.1201676, b3 = 0.937298; F(x) = 1 при x і z2. A3: F(x) = 1- 1/2 (1 + c1x + c2x2 + c3x3 + c4x4+ c4x5+ c4x6)-16 + e(x),
|e (x)| < 1.5ґ10-7, 0 Ј x < z3 = 5.4
c1 = 0.0498674370, c4 = 0.0000380036,
c2 = 0.0211410061, c5 = 0.0000488906,
c3 = 0.0032776263, c6 = 0.0000053830;
F(x) = 1 при x і z3.
A4: F(x) = 1- j (x) (d1t + d2t2 + d3t3 + d4t4 + d5t5) + e (x),
|e(x)| < 7.5ґ10-8, 0 Ј x < z4 = 5.6,
d1 = 0.319381530, d4 = -1.821255978,
d2 = -0.356563782, d5 = 1.330274429, d3 = 1.781477937;
F(x) = 1 при x і z4.
Приведу «до кучи» аппроксимации, позволяющие находить квантили нормального распределения, т.е. значения zq, для которых F(zq) = q.

Z1: ,

|e (x)| < 3*10-3, 0 Ј q < 0.5,

a0 = 2.30753, b1 = 0.99229,
a1 = 0.27061, b2 = 0.04481.
Z2: 
 
|e (x)| < 4.5*10-4, 0 Ј q < 0.5,
c0 = 2.515517, d1 = 1.432788,
c1 = 0.802853, d2 = 0.189269,
c2 = 0.010328, d3 = 0.001308.
Первое из этих разложений было использовано в A-алгоритмах для оценки того xe , после которого можно считать, что F(x) = 1.

Для вычисления F(x) с заранее фиксированной точностью легко придумать и другие алгоритмы; например, можно попросту посчитать интеграл – скажем, по формуле Симпсона. Здесь приведены наиболее экономные из всех известных мне способов.
Вверх 
Назад Оглавление Вперед

На правах рекламы
Советую линзы на месяц цена хорошая.