К разделу 'Математика' сайта 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) с заранее фиксированной точностью легко придумать и другие алгоритмы; например, можно попросту посчитать интеграл – скажем, по формуле Симпсона. Здесь приведены наиболее экономные из всех известных мне способов.
Вверх 
Назад Оглавление Вперед

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