Перейти к содержанию

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

Материал из Викиверситета

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

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


Определение. Вычислительный алгоритм называется корректным, если:
  1. Он позволяет после выполнения конечного числа элементарных для вычислительной машины операций преобразовать любое входное в результат .
  2. Результат устойчив по отношению к малым возмущениям входных данных.
  3. Результат обладает вычислительной устойчивостью.


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

Определение. Алгоритм называется вычислительно устойчивым, если вычислительная погрешность результата стремитсяк нулю при ( - машинная погрешность)


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

Определение. Вычислительный алгоритм называют хорошо обусловленным, если малые относительные погрешности округления (характеризуемые числом ) приводят к малой относительной вычислительной погрености результата


Если , то - число обусловленности алгоритма. Алгоритм плохо обусловлен, если .

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

[править]

Предполагаем, что - невырожденная ( задача корректна). - приближенное решение задачи. погрешность . Невязка

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


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

Скалярное произведение: . Погрешности: ,

Определение. Сходимость по норме: - последовательность векторов при , если при .


Норма матрицы . Свойства:

Это подчиненные нормы

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

[править]

\begin{lemma} , где \end{lemma}

Доказательство.


Теорема. - точное решение системы , где - приближенное к .

Тогда верно: , где

Доказательство. Здесь . Из леммы: . Разделим на :

- абсолютное число обусловленности для . - естественное число обусловленности (относительное). - число обусловленности.


Теорема. . Факты:
Теорема. - точное решение. - приближено заданная матрица . Тогда , где
Доказательство.


Метод Гаусса

[править]

Прямой ход:

1-й шаг - пусть . Найдем . Из уравнений вычитаем первоеб домноженное на . Получаем:

2-й шаг - пусть

k-й шаг:

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

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

Из последнего уравнения находим , подставляем в предпоследнее, находим .

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

1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний

k.

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

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

[править]

После первого шага получаем . Введем:

Начальная система: .

- верхняя треугольная матрица .

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

  1. - нижние треугольные матрицы
  2. - тоже, только у вместо <<->> стоит <<+>>

Теорема. Если все главные миноры матрицы , то нижняя треугольная матрица вида и верхняя треугольная матрица такие, что .

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

  1. преобразуем в
  2. Решаем систему

Количество действий:

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

[править]
  1. на k-м шаге в качестве главного элемента выбираем максимальный по модулю коэффициент и переставляем строки.
  2. на каждом шаге выбираем максимальный по модулю коэффициент из строк с номерами и переставляем строки (столбцы)

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

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

[править]

, - симметричная (), положительно определенная ( - скалярное произведение на ) Проверка:

  1. Все главные миноры положительны
  2. - диагональное преобладание
  3. - столбцовое преобладание

Специальное - разложение: .

После получения этого разложения решаем . Это решение требует действий

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

[править]

Вывод:

Алгоритм

Количество операций: .

Теорема. Пусть . Тогда и
Доказательство.

Пусть и для некоторого . Тогда , и


Тяпикина

[править]

Накохова

[править]

Ивницкий

[править]

Струкова

[править]

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

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


Калугина

[править]

Шульц

[править]

Байчоров

[править]

Татар

[править]

Ганзикова

[править]