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

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

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

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

(1)

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

(2)

и положим

(3)

Вычислив y(x) в точках x₀, x₁, x₂, x₃, получаем четыре нелинейных уравнения для определения констант c₀, c₁, c₂, c₃, p:

(4)

Полученная система уравнений совместна относительно неизвестных c₀, c₁, c₂, c₃ (константу p пока считаем известной) тогда и только тогда, когда детерминант

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

(5) f(p) = A₀(1+px₀)³ + A₁(1+px₁)³ +

A₂(1+px₂)³ + A₃(1+px₃)³ = 0, в котором A₀, A₁, A₂ и A₃ известны. Для определения корней этого уравнения используется какая-нибудь стандартная процедура, например, метод Ньютона. В работе [10] описаны причины, по которым в качестве p следует выбирать наименьший действительный корень уравнения (5).

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

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

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

A1: F(x) = 1-1/2(1 + a₁x + a₂x² + a₃x³ + a₄x⁴)^-4 + e(x),

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

a₁ = 0.196854, a₃ = 0.000344,
a₂ = 0.115194, a₄ = 0.019527; F(x) = 1 при x і z₁. A2: F(x) = 1- j(x) (b₁t + b₂t² + b₃t³) + e (x),

|e(x)| < 10^-5, 0 Ј x < z₂ = 4.27

b₁ = 0.4361836, b₂ = -0.1201676, b₃ = 0.937298; F(x) = 1 при x і z₂. A3: F(x) = 1- 1/2 (1 + c₁x + c₂x² + c₃x³ + c₄x⁴+ c₄x⁵+ c₄x⁶)^-16 + e(x),

|e (x)| < 1.5ґ10^-⁷, 0 Ј x < z₃ = 5.4

c₁ = 0.0498674370, c₄ = 0.0000380036,
c₂ = 0.0211410061, c₅ = 0.0000488906,
c₃ = 0.0032776263, c₆ = 0.0000053830; F(x) = 1 при x і z₃. A4: F(x) = 1- j (x) (d₁t + d₂t² + d₃t³ + d₄t⁴ + d₅t⁵) + e (x),

|e(x)| < 7.5ґ10^-8, 0 Ј x < z₄ = 5.6,

d₁ = 0.319381530, d₄ = -1.821255978,
d₂ = -0.356563782, d₅ = 1.330274429, d₃ = 1.781477937; F(x) = 1 при x і z₄. Приведу «до кучи» аппроксимации, позволяющие находить квантили нормального распределения, т.е. значения z_q, для которых F(z_q) = q.

Z1: ,

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

a₀ = 2.30753, b₁ = 0.99229,
a₁ = 0.27061, b₂ = 0.04481. Z2:

|e (x)| < 4.5*10^-4, 0 Ј q < 0.5,

c₀ = 2.515517, d₁ = 1.432788,
c₁ = 0.802853, d₂ = 0.189269,
c₂ = 0.010328, d₃ = 0.001308. Первое из этих разложений было использовано в A-алгоритмах для оценки того x_e , после которого можно считать, что F(x) = 1.

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