Просмотр кода страницы Информационные технологии в лингвистике/Лингвистика в электронных энциклопедиях/Песочница

===Корректность алгоритмов===
{{Определение|Вычислительный алгоритм - точное предписание действий над входными данными, задающее вычислительный процесс, направленный на преобразование произвольных входных данных <math>x \in X</math> в полностью определенный этими входными данными результат.
}}

{{Определение|Вычислительный алгоритм называется корректным, если:

# Он позволяет после выполнения конечного числа элементарных для вычислительной машины операций преобразовать любое входное <math>x \in X</math> в результат <math>y</math>.
# Результат <math>y</math> устойчив по отношению к малым возмущениям входных данных.
# Результат <math>y</math> обладает вычислительной устойчивостью.

}}
2. - это устойчивость по входнымм данным. Означает то, что результат непрерывным образом зависит от входных данных при условии, что отсутствует вычислительная погрешность.
{{Определение|Алгоритм называется вычислительно устойчивым, если вычислительная погрешность результата стремитсяк нулю при <math>\varepsilon_M \to 0</math> (<math>\varepsilon_m</math> - машинная погрешность)
}}
Если алгоритм устойчив по входным данным и вычислительно устойчив, то он называется устойчивым.
{{Определение|Вычислительный алгоритм называют хорошо обусловленным, если малые относительные погрешности округления (характеризуемые числом <math>\varepsilon_M</math>) приводят к малой относительной вычислительной погрености <math>\delta(y^*)</math> результата <math>y^*</math>
}}
Если <math>\delta(y^*) \le \nu_A \varepsilon_M</math>, то <math>\nu_A</math> - число обусловленности алгоритма. Алгоритм плохо обусловлен, если <math>\nu_A \gg 1</math>.

==Прямые методы решения систем линейных алгебраических уравнений.==
:<math>\begin{cases}a_{11} x_1 + a_{12} x_2 + ... + a_{1m} x_m = b_1 \\
\dots \\
a_{m1} x_1 + a_{m2} x_2 + ... + a_{mm} x_m = b_m \end{cases}</math>

:<math>A = \begin{pmatrix}a_{11} & \dots & a_{1m} \\ \vdots & \ddots & \vdots \\ a_{m1} & \dots & a_{mm}\end{pmatrix} \quad x = \begin{pmatrix}x_1 \\ \vdots \\ x_m\end{pmatrix} \quad b = \begin{pmatrix}x_1 \\ \vdots \\ x_m\end{pmatrix}</math>

<math>Ax = b</math>
Предполагаем, что <math>A</math> - невырожденная (<math>\Rightarrow</math> задача корректна). <math>x^* = (x_1^* \dots x_m^*)^T</math> - приближенное решение задачи.
погрешность <math>e = x - x^*</math>. Невязка <math>r = b - Ax^* \Rightarrow r = Ax - Ax^* = A(x - x^*) \Rightarrow e = A^{-1}r</math>

{{Определение|<math>\|x\|</math> называется нормой вектора <math>x</math>, если обладает свойствами:

# <math>\|x\| \ge 0</math>, <math>\|x\| = 0 \Leftrightarrow x = 0</math>
# <math>\|A x\| = |A| \|x\|  \forall x \forall A</math>
# <math>\|x + y\| \le \|x\| + \|y\|  \forall x, y</math>

}}
Три варианта задания нормы:

:<math>\|x\|_1 = \sum_{i=1}^m |x_i| , \quad \|x\|_2 = (\sum_{i=1}^m |x_i|^2)^{\frac 1 2} , \quad \|x\|_{\infty} = \max{1 \le i \le m} |x_i|</math>

Скалярное произведение: <math>(x,y) = x_1 y_1 + ... + x_m y_m</math>. Погрешности: <math>\delta(x^*) = \frac{\|x - x^*\|}{\|x\|}</math>, <math>\Delta(x^*) = \|x - x^*\|</math>

{{Определение|Сходимость по норме: <math>\{x^{(n)}\}_{n = 1}^{\infty}</math> - последовательность векторов <math>x^{(n)} \to x</math> при <math>n \to \infty</math>, если <math>\Delta(x^{(n)}) = \|x^{(n)} - x\| \to 0</math> при <math>n \to \infty</math>.
}}

Норма матрицы <math>\|A\| = \max{x \ne 0} \frac{\|Ax\|}{\|x\|}</math>. Свойства:

# <math>\|A\| \ge 0 \quad \|A\| = 0 \Leftrightarrow A = 0</math>
# <math>\|A A\| = |A| \|A\|  \forall A, A</math>
# <math>\|A + B\| \le \|A\| + \|B\|</math>
# <math>\|A \cdot B\| \le \|A\| \cdot \|B\|</math>
# <math>\|Ax\| \le \|A\| \cdot \|x\| \quad (\|x\| \ne 0 \Rightarrow \frac{\|Ax\|}{\|x\|} \le \|A\| - \text{из определения})</math>

:<math>\|A\|_1 = \max{1 \le j \le m} \sum_{i=1}^m |a_{ij}|, \quad \|A\|_2 = \max{1 \le j \le m} \sqrt{\lambda_j (A^T A)}, \quad \|A\|_{\infty} = \max{1 \le j \le m} \sum_{i=1}^m |a_ji|</math>

Это подчиненные нормы <math>\|A\|_E = \sqrt{\sum_{i,j = 1}^{m} \|a_ij\|^2}</math>

===Обусловленность задачи решения СЛАУ===
\begin{lemma}
<math>\Delta(x^*) \le \|A^{-1}\| \cdot \|r\|</math>, где <math>r = b - Ax^*</math>
\end{lemma}

{{Доказательство|<math>x - x^* = e = A^{-1} r \Rightarrow \Delta(x^*) = \|x -x^*\| = \|A^{-1}r\| \le \|A^{-1}\| \cdot \|r\|</math>
}}

{{МатТеорема|<math>x^*</math> - точное решение системы <math>Ax^* = b^*</math>, где <math>b^*</math> - приближенное к <math>b</math>.
Тогда верно: <math>\Delta(x^*) \le \nu_{\Delta} \Delta(b^*) \quad \delta(x^*) \le \nu_{\delta} \delta(b*)</math>, где <math>\nu_{\Delta} = \|A^{-1}\|, \nu_{\delta} = \|A^{-1}\| \cdot \|b\| / \|x\|</math>
}}

{{Доказательство|Здесь <math>r = b - Ax^* = b - b^*</math>. Из леммы: <math>\Delta(x^*) \le \|A^{-1}\| \cdot \Delta(b^*)</math>. Разделим на <math>\|x\|</math>: <math>\frac{\Delta(x^*)}{\|x\|} \le \frac{\|A^{-1}\| \cdot \|b\|}{\|x\|} \cdot \frac{\Delta(b^*)}{\|b\|}</math>

<math>\nu_{\Delta} = \|A^{-1}\|</math> - абсолютное число обусловленности для <math>Ax = b</math>. <math>\nu_{\delta} = \nu{\delta}(x) = \frac{\|A^{-1}\| \cdot \|b\|}{\|x\|}</math> - естественное число обусловленности (относительное). <math>\max{x \ne 0} \nu_{\delta}(x) = \|A^{-1}\| \cdot \|A\| = \nu(A) = cond(A)</math> - число обусловленности.
}}

{{МатТеорема|<math>\delta(x^*) \le cond(A) \cdot \delta(b^*)</math>. Факты:

# <math>cond(E) = 1 \quad (E^{-1} = E ,  \|E\| = 1)</math>
# <math>cond(A) \ge 1 \quad (E = A^{-1}A ,  \|E\| \le \|A^{-1}\| \cdot \|A\|)</math>
# <math>\forall A \ne 0 : cond(A A) = cond(A)  \quad (\|A A\| \cdot \|A A^{-1}\| = |A| \|A\| \cdot |A|^{-1} \|A^{-1}\|)</math>

}}

{{МатТеорема|<math>x^*</math> - точное решение. <math>A_* x^* = b</math> - приближено заданная матрица <math>A_*</math>. Тогда <math>\delta^*(x^*) \le cond(A) \cdot \delta(A_*)</math>, где <math>\delta^*(x^*) = \frac{\|x - x^*\|}{\|x^*\|},  \delta(A_*) = \frac{\|A - A_*\|}{\|A\|}</math>
}}
{{Доказательство|<math>r = b - Ax^* = A_* x^* - A x^* = (A_* - A) x^*</math>

<math>\delta^*(x^*) = \frac{\|x - x^*\|}{\|x^*\|} \le \|A^{-1}\| \cdot \|(A_* - A) x^*\| / \|x^*\| \le \frac{\|a^{-1}\| \cdot \|A_* - A\| \cdot \|x^*\|}{\|x^*\|} = cond(A) \cdot \delta(A_*)</math>
}}

===Метод Гаусса===
Прямой ход:

1-й шаг - пусть <math>a_{11} \ne 0</math>. Найдем <math>\mu_{i1} = \frac{a_{i1}}{a{11}},  i = \overline{2, m}</math>. Из <math>2..m</math> уравнений вычитаем первоеб домноженное на <math>\mu_{i1}</math>. Получаем:

:<math>\begin{matrix}
a_{11} x_1 + a_{12} x_2 +  \dots + a_{1m} x_m =  b_{1} \\
a_{22}^{(1)} x_2  +  \dots +  a_{2m}^{(1)} x_m =  b_2^{(1)} \\
\dots   \\
a_{m2}^{(1)} x_2  +  \dots +  a_{mm}^{(1)} x_m =  b_m^{(1)}
\end{matrix}</math>

<math>a_{ij}^{(1)} = a_{ij} - \mu_{i1} a_{ij}, \quad b_i^{(1)} = b_i - \mu_{i1}b_1</math>

2-й шаг - пусть <math>a_{22}^{(1)} \ne 0, \quad \mu_{i2} = \frac{a_{i2}^{(1)}}{a_{22}^{(1)}}</math>

k-й шаг: <math>a_{kk}^{(k-1)} \ne 0, \quad \nu_{ik} = \frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}},  i = \overline{k+1, m}</math>

За (m-1) шаг получаем:

:<math>\begin{matrix}
a_{11} x_1 + a_{12} x_2 + a_{33} x_3 +  \dots + a_{1m} x_m =  b_{1} \\
a_{22}^{(1)} x_2 + a_{33}^{(1)} x_3 +  \dots +  a_{2m}^{(1)} x_m =  b_2^{(1)} \\
a_{33}^{(2)} x_3  +  \dots +  a_{2m}^{(2)} x_m =  b_2^{(2)} \\
\dots   \\
a_{mm}^{(m-1)} x_m =  b_m^{(m-1)}
\end{matrix}</math>

Обратный ход:

Из последнего уравнения находим <math>x_m</math>, подставляем в предпоследнее, находим <math>x_{m-1}</math>.
<math>x_m = b_m^{(m-1)} / a_{mm}^{(m-1)}, x_k = (b_k^{(k-1)} - a_{k,k+1}^{(k-1)} x_{k+1} - ... - a_{km}^{(k-1)} x_m) / a_{kk}^{k-1},  k = \overline{m-1, 1}</math>

Трудоемкость:

1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний <math>\Rightarrow Q_1 = 2(m-1)^2 + 3(m-1)</math>

k. <math>Q_k = 2(m - k)^2 + 3(m - k)</math>

<math>Q = \sum_{k = 1}^{n-1} Q_k = 2 \sum_{k = 1}^{m - 1} (m - k)^2 + 3 \sum_{k = 1}^{m - 1} (m - k) = 2 \sum_{k = 1}^{m - 1} k^2 + 3 \sum_{k = 1}^{m - 1} k = \frac{2(m -1) m (2m -1)}{6} + \frac{3(m-1)m}{2} \approx \frac 2 3 m^3</math> 

Обратный ход: <math>m^2</math> операций.
Необходимость выбора главных элемнтов: главный элемент не должен быть равен нулю. Если он близок к нулю, растет погрешность (это для ЭВМ).

===Матричная форма метода Гаусса. (LU - разложение)===
После первого шага получаем <math>A^{(1)}x = b^{(1)}</math>. Введем:

:<math>M_1 = \begin{pmatrix}1 & 0 & 0 & \dots & 0 \\ - \mu_{21} & 1 & 0 & \dots & 0 \\ - \mu_{31} & 0 & 1 & \dots & 0 \\ \dots \\ - \mu_{m1} & 0 & 0 & \dots & 1 \end{pmatrix}

M_2 = \begin{pmatrix}1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & - \mu_{32} & 1 & \dots & 0 \\ \dots \\0 & - \mu_{m2} & 0  & \dots & 1 \end{pmatrix}
</math>

:<math>M_{m-1} = \begin{pmatrix}1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ 0 & 0 & \dots & 0 & 0 \\ \dots \\0 & 0  & \dots & -\mu_{m, m - 1} & 1 \end{pmatrix}
</math>

:<math>A^{(1)} = M_1 A,  b^{(1)} = M_1 b, \quad A^{(m-1)} = M_{m-1} A^{(m-2)},  b^{(m-1)} = M_{m-1} b^{(m-2)}</math>

Начальная система: <math>M_{m-1} \cdot ... \cdot M_2 \cdot M_1 \cdot A x = M_{m-1} \cdot ... \cdot M_2 \cdot M_1 \cdot b</math>.

<math>M_{m-1} \cdot ... \cdot M_2 \cdot M_1 \cdot A</math> - верхняя треугольная матрица <math>= A^{(m-1)}</math>.

<math>L = M_1^{-1}M_2^{-1} ... M_{m-1}^{-1} = \begin{pmatrix}1 & 0 & 0 & ... & 0 \\ \mu_{21} & 1 & 0 & ... & 0 \\ \mu_{31} & \mu_{32} & 1 & ... & 0 \\ \dots \\  \mu_{m1} & \mu_{m2} & \mu_{m3} & ... & 1\end{pmatrix}</math>

Свойства элементарных матриц:

# <math>\det M_i = 1</math>
# <math>M_i</math> - нижние треугольные матрицы
# <math>M_i^{-1}</math> - тоже, только у <math>\mu</math> вместо &lt;&lt;-&gt;&gt; стоит &lt;&lt;+&gt;&gt;

<math>A = LU</math>

{{МатТеорема|Если все главные миноры матрицы <math>A \ne 0</math>, то <math>\exists !</math> нижняя треугольная матрица <math>L</math> вида <math>(1)</math> и верхняя треугольная матрица <math>U</math> такие, что <math>A = LU</math>.
}}
Использование:

# преобразуем <math>b</math> в <math>b^{(m-1)} \quad b^{(m-1)} = M_{m-1} ... M_2 M_1 b</math>
# Решаем систему <math>Ux = b^{(m-1)}</math>

Количество действий: <math>\frac 2 3 m^3 + 2 m^2</math>

===Модификации Гаусса===

# на k-м шаге в качестве главного элемента выбираем максимальный по модулю коэффициент <math>a_{i_k,k}</math> и переставляем строки.
# на каждом шаге выбираем максимальный по модулю коэффициент из строк с номерами <math>i = k..m</math> и переставляем строки (столбцы)

Масштабирование - делим каждое уравнение на наибольший по модулю коэффициент.

===Метод Холецкого===
<math>Ax = b</math>, <math>A</math> - симметричная (<math>A = A^T</math>), положительно определенная (<math>\forall x \ne 0 : (Ax, x) > 0</math> - скалярное произведение <math>Ax</math> на <math>x</math>)
Проверка:

# Все главные миноры положительны
# <math>|a_{ii}| > \sum_{j\ne i} |a_{ij}|</math> - диагональное преобладание
# <math>|a_{jj}| > \sum_{i \ne j} |a_{ij}|</math> - столбцовое преобладание

Специальное <math>LU</math> - разложение: <math>A = LL^T</math>.

:<math>L = \begin{pmatrix}l_{11} & 0 & \dots & 0 \\ l_{21} & l_{22} & \dots & 0 \\ \dots \\ l_{m1} & l_{m2} & \dots & l_{mm}\end{pmatrix}</math>

:<math>\begin{matrix}
& l_{11}^2 = a_{11} &  \\
& l_{i1}l_{11} = a_{i1} & i = \overline{2,m} \\
& l_{21}^2 + l_{22}^2 = a_{i2} &  \\
& l_{i1}l_{21} + l_{i2}l_{22} = a_{i2} & i = \overline{3,m} \\
& \dots & \\
& l_{k1}^2 + l_{k2}^2 + ... + l_{kk}^2= a_{kk} &  \\
& l_{i1}l_{k1} + ... + l_{ik}l_{kk} = a_{ik} & i = \overline{k+1,m} \\
& \dots & \\
& l_{m1}^2 + ... + l_{mm}^2= a_{mm} & 
\end{matrix} \Rightarrow </math>

:<math>\Rightarrow \begin{matrix}
& l_{11} = \sqrt{a_{11}} &  \\
& l_{i1} = a_{i1}/l_{11} & i = \overline{2,m} \\
& l_{22} = \sqrt{a_{i2} - l_{21}^2} &  \\
& l_{i2} = (a_{i2} - l_{i1}l_{21}) / l_{22} & i = \overline{3,m} \\
& \dots & \\
& l_{kk} = \sqrt{a_{kk} - l_{k1}^2 - ... - l_{k,k - 1}^2} &  \\
& l_{ik} = (a_{ik} - l_{i1}l_{k1} - ... - l_{i,k - 1}l_{k,k - 1}) / l_{kk} & i = \overline{k+1,m} \\
& \dots & \\
& l_{mm} = \sqrt{a_{mm} - l_{m1}^2 - ... - l_{m,m - 1}^2} & 
\end{matrix}</math>

После получения этого разложения решаем <math>Ly = b,  L^Tx = y</math>. Это решение требует <math>2m^2</math> действий

===Метод Прогонки===
:<math>\begin{matrix}
&b_1 x_1 + c_1 x_2 & = d_1 \\
&a_2 x_1 + b_2 x_2 + c_2 x_3 & = d_2 \\
&\dots \\
&a_i x_{i-1} + b_i x_i + c_i x_{i+1} & = d_i \\
&\dots \\
&a_{m-1} x_{m-2} + b_{m-1} x_{m-1} + c_{m-1} x_{m} & = d_{m-1} \\
&a_{m} x_{m-1} + b_{m} x_{m} & = d_m \\
\end{matrix}</math>

Вывод:

:<math>\begin{matrix}
x_1 = A_1 x_2 + \beta_1 & A_1 = - \frac{c_1}{b_1} & \beta_1 = \frac{d_1}{b_1} \\
x_2 = A_2 x_3 + \beta_2  &  A_2 = - \frac{c_2}{b_2 + a_2 A_1}  &  \beta_2 = \frac{d_2 - a_2 \beta_1}{b_2 + a_2 A_1} \\
\dots \\
x_i = A_i x_{i+1} + \beta_i  &  A_i = - \frac{c_i}{b_i + a_i A_{i-1}}  &  \beta_i = \frac{d_i - a_i \beta_{i-1}}{b_i + a_i A_{i-1}} \\
\dots \\
x_{m-1} = A_{m-1}x_m + \beta_{mm-1}
\end{matrix}</math>

:<math>m : a_m (a_{m-1} x_m + \beta_{m-1}) + b_m x_m \Rightarrow x_m = \beta_m = \frac{d_m - a_m \beta_{m-1}}{b_m + a_m A_{m-1}}</math>

Алгоритм

:<math>\begin{matrix}
\text{Прямой ход:} \\
i = 1 & A_i = - \frac{c_i}{\gamma_i} & \beta_i = \frac{d_i}{\gamma_i} & \gamma_i = b_i \\
i = 2..m-1 & A_i = - \frac{c_i}{\gamma_i} & \beta_i = \frac{d_i - a_i \beta_{i-1}}{\gamma_i} & \gamma_i = b_i + a_i A_{i-1} \\
i = m &  & \beta_i = \frac{d_i - a_i \beta_{i-1}}{\gamma_i} & \gamma_i = b_i + a_i A_{i-1} \\
\end{matrix}</math>

:<math>\begin{matrix}
\text{Обратный ход:} \\
i = m & x_m = b_m \\
i = m - 1 .. 1 & x_i = a_i x_{i+1} + \beta_i\\
\end{matrix}</math>

Количество операций: <math>Q = 8m</math>.

{{МатТеорема|Пусть <math>|b_k| \ge |a_k| + |c_k|,  |b'_k| > |a_k|,  (1 \le k \le m)</math>. Тогда <math>\gamma_i \ne 0</math> и <math>A_i \le 1</math> <math>\forall i = 1,2,...,m</math>
}}

{{Доказательство|<math>\gamma_1 = b_1 \ne 0,  |A_1| = \frac{|c_1|}{|b_1|} \le 1 </math>
Пусть <math>\gamma_{k-1} \ne 0</math> и <math>|\lambda_{k-1}| \le 1</math> для некоторого <math>k > 1</math>. Тогда <math>|\gamma_k| = |b_k + a_k A_{k-1}| \ge |b_k| - |a_k| |A_{k-1}| \ge |b_k| - |a_k| > 0</math>, <math>|\gamma_k| \ge |c_k| \Rightarrow \gamma_k \ne 0</math> и <math>|A_k| = \frac{|c_k|}{|\gamma_k|} \le 1</math>
}}

== Тяпикина ==

== Накохова ==


== Ивницкий ==


== Струкова ==
При создании страниц важно завлечь посетителя. Не забывайте, что в среднем человек находится на веб-странице 3—5 секунд, если он за это время не нашёл нужного, то он уходит со страницы. Следовательно, страницы должны быть:

1.'''Полезными'''. Отсутствие сути никаким оформлением не прикроешь. Обратное неверно. Пример — Библиотека Мошкова
2.'''Небольшими'''. Даже если контент интересен, то 10 экранных страниц интересного контента на одной странице сайта это слишком. ''2—3 экрана это максимум''. Большие страницы лучше разбить на несколько и связать гипертекстовыми ссылками.
3.'''Структурными'''. ''Структурный текст лучше воспринимается'', и в нём легче найти необходимую информацию. Самое важное должно быть выделено. Не злоупотребляйте выделением — когда выделено всё, значит ничто не выделено.


== Калугина ==


== Шульц ==




==Байчоров==



== Татар ==
== Ганзикова ==

[[Категория:Прикладная лингвистика]]
[[Категория:Информационные технологии в лингвистике|*]]