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

Корректность алгоритмов

Определение. Вычислительный алгоритм - точное предписание действий над входными данными, задающее вычислительный процесс, направленный на преобразование произвольных входных данных $x\in X$ в полностью определенный этими входными данными результат.

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

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

2. - это устойчивость по входнымм данным. Означает то, что результат непрерывным образом зависит от входных данных при условии, что отсутствует вычислительная погрешность.

Определение. Алгоритм называется вычислительно устойчивым, если вычислительная погрешность результата стремитсяк нулю при ${\epsilon }_M\to 0$ (${\epsilon }_m$ - машинная погрешность)

Если алгоритм устойчив по входным данным и вычислительно устойчив, то он называется устойчивым.

Определение. Вычислительный алгоритм называют хорошо обусловленным, если малые относительные погрешности округления (характеризуемые числом ${\epsilon }_M$) приводят к малой относительной вычислительной погрености $\delta (y^{\ast })$ результата $y^{\ast }$

Если $\delta (y^{\ast })\le {\nu }_A{\epsilon }_M$, то ${\nu }_A$ - число обусловленности алгоритма. Алгоритм плохо обусловлен, если ${\nu }_A\gg 1$.

Прямые методы решения систем линейных алгебраических уравнений.

$\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\mathrm{...}+a_{1m}{x}_m=b_1\\ \dots \\ a_{m1}{x}_1+a_{m2}{x}_2+\mathrm{...}+a_{mm}{x}_m=b_m\end{array}$

$A=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1m}\\ ⋮& \ddots & ⋮\\ a_{m1}& \dots & a_{mm}\end{array}\right)x=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_m\end{array}\right)b=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_m\end{array}\right)$

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

Определение. $\Vert x\Vert$ называется нормой вектора $x$, если обладает свойствами:

1. $\Vert x\Vert \ge 0$, $\Vert x\Vert =0\iff x=0$
2. $\Vert Ax\Vert =|A|\Vert x\Vert \mathrm{\forall }x\mathrm{\forall }A$
3. $\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert \mathrm{\forall }x,y$

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

$\Vert x{\Vert }_1=\sum _{i=1}^m|x_i|,\Vert x{\Vert }_2=(\sum _{i=1}^m|x_i{|}^2{)}^{\frac{1}{2}},\Vert x{\Vert }_{\mathrm{\infty }}=max1\le i\le m|x_i|$

Скалярное произведение: $(x,y)=x_1{y}_1+\mathrm{...}+x_m{y}_m$. Погрешности: $\delta (x^{\ast })=\frac{\Vert x-x^{\ast }\Vert }{\Vert x\Vert }$, $\mathrm{\Delta }(x^{\ast })=\Vert x-x^{\ast }\Vert$

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

Норма матрицы $\Vert A\Vert =maxx\ne 0\frac{\Vert Ax\Vert }{\Vert x\Vert }$. Свойства:

1. $\Vert A\Vert \ge 0\Vert A\Vert =0\iff A=0$
2. $\Vert AA\Vert =|A|\Vert A\Vert \mathrm{\forall }A,A$
3. $\Vert A+B\Vert \le \Vert A\Vert +\Vert B\Vert$
4. $\Vert A\cdot B\Vert \le \Vert A\Vert \cdot \Vert B\Vert$
5. $\Vert Ax\Vert \le \Vert A\Vert \cdot \Vert x\Vert (\Vert x\Vert \ne 0\Rightarrow \frac{\Vert Ax\Vert }{\Vert x\Vert }\le \Vert A\Vert -\text{из определения})$

$\Vert A{\Vert }_1=max1\le j\le m\sum _{i=1}^m|a_{ij}|,\Vert A{\Vert }_2=max1\le j\le m\sqrt{{\lambda }_j(A^{T}A)},\Vert A{\Vert }_{\mathrm{\infty }}=max1\le j\le m\sum _{i=1}^m|a_{j}i|$

Это подчиненные нормы $\Vert A{\Vert }_E=\sqrt{\sum _{i,j=1}^m\Vert a_{i}j{\Vert }^2}$

Обусловленность задачи решения СЛАУ

\begin{lemma} $\mathrm{\Delta }(x^{\ast })\le \Vert A^{-1}\Vert \cdot \Vert r\Vert$, где $r=b-A{x}^{\ast }$ \end{lemma}

Доказательство. $x-x^{\ast }=e=A^{-1}r\Rightarrow \mathrm{\Delta }(x^{\ast })=\Vert x-x^{\ast }\Vert =\Vert A^{-1}r\Vert \le \Vert A^{-1}\Vert \cdot \Vert r\Vert$

Теорема. $x^{\ast }$ - точное решение системы $A{x}^{\ast }=b^{\ast }$, где $b^{\ast }$ - приближенное к $b$.

Тогда верно: $\mathrm{\Delta }(x^{\ast })\le {\nu }_{\mathrm{\Delta }}\mathrm{\Delta }(b^{\ast })\delta (x^{\ast })\le {\nu }_{\delta }\delta (b\ast )$, где ${\nu }_{\mathrm{\Delta }}=\Vert A^{-1}\Vert ,{\nu }_{\delta }=\Vert A^{-1}\Vert \cdot \Vert b\Vert /\Vert x\Vert$

Доказательство. Здесь $r=b-A{x}^{\ast }=b-b^{\ast }$. Из леммы: $\mathrm{\Delta }(x^{\ast })\le \Vert A^{-1}\Vert \cdot \mathrm{\Delta }(b^{\ast })$. Разделим на $\Vert x\Vert$: $\frac{\mathrm{\Delta }(x^{\ast })}{\Vert x\Vert }\le \frac{\Vert A^{-1}\Vert \cdot \Vert b\Vert }{\Vert x\Vert }\cdot \frac{\mathrm{\Delta }(b^{\ast })}{\Vert b\Vert }$

${\nu }_{\mathrm{\Delta }}=\Vert A^{-1}\Vert$ - абсолютное число обусловленности для $Ax=b$. ${\nu }_{\delta }=\nu \delta (x)=\frac{\Vert A^{-1}\Vert \cdot \Vert b\Vert }{\Vert x\Vert }$ - естественное число обусловленности (относительное). $maxx\ne 0{\nu }_{\delta }(x)=\Vert A^{-1}\Vert \cdot \Vert A\Vert =\nu (A)=cond(A)$ - число обусловленности.

Теорема. $\delta (x^{\ast })\le cond(A)\cdot \delta (b^{\ast })$. Факты:

1. $cond(E)=1(E^{-1}=E,\Vert E\Vert =1)$
2. $cond(A)\ge 1(E=A^{-1}A,\Vert E\Vert \le \Vert A^{-1}\Vert \cdot \Vert A\Vert )$
3. $\mathrm{\forall }A\ne 0:cond(AA)=cond(A)(\Vert AA\Vert \cdot \Vert A{A}^{-1}\Vert =|A|\Vert A\Vert \cdot |A{|}^{-1}\Vert A^{-1}\Vert )$

Теорема. $x^{\ast }$ - точное решение. $A_{\ast }{x}^{\ast }=b$ - приближено заданная матрица $A_{\ast }$. Тогда ${\delta }^{\ast }(x^{\ast })\le cond(A)\cdot \delta (A_{\ast })$, где ${\delta }^{\ast }(x^{\ast })=\frac{\Vert x-x^{\ast }\Vert }{\Vert x^{\ast }\Vert },\delta (A_{\ast })=\frac{\Vert A-A_{\ast }\Vert }{\Vert A\Vert }$

Доказательство. $r=b-A{x}^{\ast }=A_{\ast }{x}^{\ast }-A{x}^{\ast }=(A_{\ast }-A)x^{\ast }$

${\delta }^{\ast }(x^{\ast })=\frac{\Vert x-x^{\ast }\Vert }{\Vert x^{\ast }\Vert }\le \Vert A^{-1}\Vert \cdot \Vert (A_{\ast }-A)x^{\ast }\Vert /\Vert x^{\ast }\Vert \le \frac{\Vert a^{-1}\Vert \cdot \Vert A_{\ast }-A\Vert \cdot \Vert x^{\ast }\Vert }{\Vert x^{\ast }\Vert }=cond(A)\cdot \delta (A_{\ast })$

Метод Гаусса

Прямой ход:

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

$\begin{array}{c}{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{array}$

$a_{ij}^{(1)}=a_{ij}-{\mu }_{i1}{a}_{ij},b_i^{(1)}=b_i-{\mu }_{i1}{b}_1$

2-й шаг - пусть $a_{22}^{(1)}\ne 0,{\mu }_{i2}=\frac{a_{i2}^{(1)}}{a_{22}^{(1)}}$

k-й шаг: $a_{kk}^{(k-1)}\ne 0,{\nu }_{ik}=\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}},i=\overline{k+1,m}$

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

$\begin{array}{c}{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{array}$

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

Из последнего уравнения находим $x_m$, подставляем в предпоследнее, находим $x_{m-1}$. $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}-\mathrm{...}-a_{km}^{(k-1)}{x}_m)/a_{kk}^{k-1},k=\overline{m-1,1}$

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

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

k. $Q_k=2(m-k{)}^2+3(m-k)$

$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$

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

Матричная форма метода Гаусса. (LU - разложение)

После первого шага получаем $A^{(1)}x=b^{(1)}$. Введем:

$M_1=\left(\begin{array}{ccccc}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{array}\right)M_2=\left(\begin{array}{ccccc}1& 0& 0& \dots & 0\\ 0& 1& 0& \dots & 0\\ 0& -{\mu }_{32}& 1& \dots & 0\\ \dots \\ 0& -{\mu }_{m2}& 0& \dots & 1\end{array}\right)$

$M_{m-1}=\left(\begin{array}{ccccc}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{array}\right)$

$A^{(1)}=M_{1}A,b^{(1)}=M_{1}b,A^{(m-1)}=M_{m-1}{A}^{(m-2)},b^{(m-1)}=M_{m-1}{b}^{(m-2)}$

Начальная система: $M_{m-1}\cdot \mathrm{...}\cdot M_2\cdot M_1\cdot Ax=M_{m-1}\cdot \mathrm{...}\cdot M_2\cdot M_1\cdot b$.

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

$L=M_1^{-1}{M}_2^{-1}\mathrm{...}{M}_{m-1}^{-1}=\left(\begin{array}{ccccc}1& 0& 0& \mathrm{...}& 0\\ {\mu }_{21}& 1& 0& \mathrm{...}& 0\\ {\mu }_{31}& {\mu }_{32}& 1& \mathrm{...}& 0\\ \dots \\ {\mu }_{m1}& {\mu }_{m2}& {\mu }_{m3}& \mathrm{...}& 1\end{array}\right)$

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

1. $det{M}_i=1$
2. $M_i$ - нижние треугольные матрицы
3. $M_i^{-1}$ - тоже, только у $\mu$ вместо <<->> стоит <<+>>

$A=LU$

Теорема. Если все главные миноры матрицы $A\ne 0$, то $\mathrm{\exists }!$ нижняя треугольная матрица $L$ вида $(1)$ и верхняя треугольная матрица $U$ такие, что $A=LU$.

Использование:

1. преобразуем $b$ в $b^{(m-1)}{b}^{(m-1)}=M_{m-1}\mathrm{...}{M}_2{M}_{1}b$
2. Решаем систему $Ux=b^{(m-1)}$

Количество действий: $\frac{2}{3}{m}^3+2m^2$

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

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

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

Метод Холецкого

$Ax=b$, $A$ - симметричная ($A=A^T$), положительно определенная ($\mathrm{\forall }x\ne 0:(Ax,x)>0$ - скалярное произведение $Ax$ на $x$) Проверка:

1. Все главные миноры положительны
2. $|a_{ii}|>\sum _{j\ne i}|a_{ij}|$ - диагональное преобладание
3. $|a_{jj}|>\sum _{i\ne j}|a_{ij}|$ - столбцовое преобладание

Специальное $LU$ - разложение: $A=L{L}^T$.

$L=\left(\begin{array}{cccc}{l}_{11}& 0& \dots & 0\\ l_{21}& l_{22}& \dots & 0\\ \dots \\ l_{m1}& l_{m2}& \dots & l_{mm}\end{array}\right)$

$\begin{array}{ccc}& 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+\mathrm{...}+l_{kk}^2=a_{kk}& \\ & l_{i1}{l}_{k1}+\mathrm{...}+l_{ik}{l}_{kk}=a_{ik}& i=\overline{k+1,m}\\ & \dots & \\ & l_{m1}^2+\mathrm{...}+l_{mm}^2=a_{mm}& \end{array}\Rightarrow$

$\Rightarrow \begin{array}{ccc}& 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-\mathrm{...}-l_{k,k-1}^2}& \\ & l_{ik}=(a_{ik}-l_{i1}{l}_{k1}-\mathrm{...}-l_{i,k-1}{l}_{k,k-1})/l_{kk}& i=\overline{k+1,m}\\ & \dots & \\ & l_{mm}=\sqrt{a_{mm}-l_{m1}^2-\mathrm{...}-l_{m,m-1}^2}& \end{array}$

После получения этого разложения решаем $Ly=b,L^{T}x=y$. Это решение требует $2m^2$ действий

Метод Прогонки

$\begin{array}{ccc}& 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{array}$

Вывод:

$\begin{array}{ccc}{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{array}$

$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}}$

Алгоритм

$\begin{array}{c}\text{Прямой ход:}\\ i=1& A_i=-\frac{c_i}{{\gamma }_i}& {\beta }_i=\frac{d_i}{{\gamma }_i}& {\gamma }_i=b_i\\ i=\mathrm{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{array}$

$\begin{array}{c}\text{Обратный ход:}\\ i=m& x_m=b_m\\ i=m-\mathrm{1..1}& x_i=a_i{x}_{i+1}+{\beta }_i\end{array}$

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

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

Доказательство. ${\gamma }_1=b_1\ne 0,|A_1|=\frac{|c_1|}{|b_1|}\le 1$

Пусть ${\gamma }_{k-1}\ne 0$ и $|{\lambda }_{k-1}|\le 1$ для некоторого $k>1$. Тогда $|{\gamma }_k|=|b_k+a_k{A}_{k-1}|\ge |b_k|-|a_k||A_{k-1}|\ge |b_k|-|a_k|>0$, $|{\gamma }_k|\ge |c_k|\Rightarrow {\gamma }_k\ne 0$ и $|A_k|=\frac{|c_k|}{|{\gamma }_k|}\le 1$

Струкова

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

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