Осевое преобразование

Картинка по запросу "pivot step"

Осевое преобразование матрицы - очень простое. Пусть дана матрица A
$A = \left( \begin{array}{ccccc} \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & a & \ldots & b & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & c & \ldots & d & \ldots \end{array} \right)$
Операция осевого преобразования c осевым элементом a (англ. pivot step) превращает её в следующую матрицу A₁
$A_1 = \left( \begin{array}{ccccc} \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & 1/a & \ldots & b/a & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & - \frac{c}{a} & \ldots & d - \frac{bc}{a} & \ldots \end{array} \right)$
Строка и столбец матрицы, на которых расположен элемент a называются осевыми строкой и столбцом.
Пошаговое осевое преобразование по главной диагонали используется для получения матрицы идентичности. Это нужно, например, для вычисления обратной матрицы.
В случае больших разреженных матриц имеет смысл задавать матрицу в виде двусвязанных ортогональных списков. Моя реализация алгоритма осевого преобразования на Java работает с матрицами такого вида из предыдущего поста. Мне понравился алгоритм вставки элементов в произвольное место такой матрицы. Он получился красивым, черт возьми. Там ведь по сути идет работа с двумя замкнутыми кольцами из односвязных элементов, в котором мы по определенному правилу меняем связи.
Весь проект для Eclipse (матрица, генератор матриц, алгоритм) можно скачать в ZIP архиве.

Разреженная матрица

Матрица называется разреженной, если в ней относительно много нулей и довольно мало значений. Ниже пример разреженной матрицы.



$\left( \begin{array}{ccccc} 1 & 2 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right)$



Разреженной матрицей удобно описывать рельеф местности. Понятно что хранить в памяти всю матрицу неэффективно. Хорошо бы оставить только "полезные значения", то есть, ненулевые. В книге Кнута "Искусство программирования" приводится пример организации матрицы в виде двусвязанных списков.
Двусвязанный список состоит

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

$\begin{array}{cc} LEFT & UP \\ COLUMN & ROW \\ VALUE \end{array} $
Реализация разреженной матрицы на Java. Я еще не тестировал её, т.к. она лишь часть алгоритма для осевого преобразования.
Элементами матрицы являются экземпляры класса MNode - и это всего лишь те самые двусвязанные списки

Основные характеристики дискретной случайной величины

Математическое ожидание ДСВ: $A = \sum\limits_{k} A_k * p_k$
Дисперсия D случайной величины вычисляется как математическое ожидание величины $(A-An)^2$, поэтому
$D = \sum\limits_{k}(k-An)^2p_k$
Среднеквадратическое отклонение $\delta = \sqrt{D}$. Смысл этой величины такой: случайная величина принимает значение не из промежутка $[A-r\delta,A+r\delta]$ с вероятностью не превышающей $1/r^2$. Например, событие $|A-An| > 2\delta$ происходит с вероятностью не больше $1/4$

Приближенное вычисление факториала

В 1730 году Джеймс Стирлинг в своей работе привел формулу приближенного вычисления факториала
$n! \approx \sqrt{2\pi n}*(\frac{n}{e})^n$
Она дает погрешность $\frac{1}{12n}$
Погрешность измерений $\delta x(n)$ это величина характеризующая отклонение приближенного значения от истинного. Т.е. $|I \index n - F\index n| \leq \delta x(n)$

Алгоритм Эвклида

Элегантный алгоритм Эвклида для поиска НОД (наименьшего общего делителя)

Интересное тождество

1+3+...+(2n-1) = n²
То есть, сумма первых n нечетных чисел равна квадрату n.

Последовательность Фибоначчи

Последовательность Фибоначии задается рекурсивным соотношением
Fn = Fn-1 + Fn-2
Формулу Nго члена вывел французский математик Боне.
Fn = [(1 + sqrt(5))/2]^2 + [(1 - sqrt(2))/2]^n / sqrt(5)
Выводится формула благодаря замечательной"золотой пропорции":
t = {1 - sqrt(5)) / 2
и её свойствам:
t² = t + 1
tⁿ = t^n-1 + t ^n-2
Если рассмотреть последовательность {tn}, то можно видеть что коэффициент n-ого члена при иррациональном слагаемом в числителе будет являться n-ым членом последовательности Фибоначчи! Реализация на Питоне этого алгоритма