Исходя из ссылки Пиллси на возведение в степень матрицы, такой, что для матрицы
<b>M</b> = [1 1]
[1 0]
, затем
<i>fib</i>(<i>n</i>) = <b>M</b><sup>n</sup><sub>1,2</sub>
Повышение матриц до степеней с помощью повторного умножения не очень эффективно.
Два подхода к возведению в матрицу - это разделяй и властвуй, что дает M n с O ( ln n ) или собственное значение декомпозиция с постоянным временем, но может привести к ошибкам из-за ограниченной точности с плавающей запятой.
Если вы хотите, чтобы точное значение превышало точность вашей реализации с плавающей запятой, вы должны использовать подход O (ln n), основанный на этом отношении:
<b>M</b><sup><i>n</i></sup> = (<b>M</b><sup><i>n</i>/2</sup>)<sup>2</sup> if <i>n</i> even
= <b>M</b>·<b>M</b><sup><i>n</i>-1</sup> if <i>n</i> is odd
Разложение по собственным значениям M находит две матрицы U и & Lambda; , такие что & Lambda; диагональна и
<b>M</b> = <b>U</b> <b>Λ</b> <b>U</b><sup>-1</sup>
<b>M</b><sup>n</sup> = ( <b>U</b> <b>Λ</b> <b>U</b><sup>-1</sup>) <sup>n</sup>
= <b>U</b> <b>Λ</b> <b>U</b><sup>-1</sup> <b>U</b> <b>Λ</b> <b>U</b><sup>-1</sup> <b>U</b> <b>Λ</b> <b>U</b><sup>-1</sup> ... n times
= <b>U</b> <b>Λ</b> <b>Λ</b> <b>Λ</b> ... <b>U</b><sup>-1</sup>
= <b>U</b> <b>Λ</b> <sup>n</sup> <b>U</b><sup>-1</sup>
Повышение диагональной матрицы
& lambda; до
n th является простым делом повышения каждого элемента в
& Lambda; до
n th, так что это дает O (1) метод повышения
M до
n th. Однако значения в
& Lambda; вряд ли будут целыми числами, поэтому возникнет некоторая ошибка.
Определение & Lambda; для нашей матрицы 2x2 как
<b>Λ</b> = [ λ<sub>1</sub> 0 ]
= [ 0 λ<sub>2</sub> ]
Чтобы найти каждый & lambda; , мы решаем
|<b>M</b> - λ<b>I</b>| = 0
что дает
|<b>M</b> - λ<b>I</b>| = -λ ( 1 - λ ) - 1
λ² - λ - 1 = 0
с использованием квадратной формулы
λ = ( -b ± √ ( b² - 4ac ) ) / 2a
= ( 1 ± √5 ) / 2
{ λ<sub>1</sub>, λ<sub>2</sub> } = { Φ, 1-Φ } where Φ = ( 1 + √5 ) / 2
Если вы прочитали ответ Джейсона, вы можете увидеть, куда это пойдет.
Решение для собственных векторов X 1 и X 2 :
if <b>X</b><sub>1</sub> = [ <b>X</b><sub>1,1</sub>, <b>X</b><sub>1,2</sub> ]
<b>M</b>.<b>X</b><sub>1 1</sub> = λ<sub>1</sub><b>X</b><sub>1</sub>
<b>X</b><sub>1,1</sub> + <b>X</b><sub>1,2</sub> = λ<sub>1</sub> <b>X</b><sub>1,1</sub>
<b>X</b><sub>1,1</sub> = λ<sub>1</sub> <b>X</b><sub>1,2</sub>
=>
<b>X</b><sub>1</sub> = [ Φ, 1 ]
<b>X</b><sub>2</sub> = [ 1-Φ, 1 ]
Эти векторы дают U :
<b>U</b> = [ <b>X</b><sub>1,1</sub>, <b>X</b><sub>2,2</sub> ]
[ <b>X</b><sub>1,1</sub>, <b>X</b><sub>2,2</sub> ]
= [ Φ, 1-Φ ]
[ 1, 1 ]
Инвертирование U с использованием
<b>A</b> = [ a b ]
[ c d ]
=>
<b>A</b><sup>-1</sup> = ( 1 / |<b>A</b>| ) [ d -b ]
[ -c a ]
так U -1 задается
<b>U</b><sup>-1</sup> = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
[ -1 Φ ]
<b>U</b><sup>-1</sup> = ( √5 )<sup>-1</sup> [ 1 Φ-1 ]
[ -1 Φ ]
Проверка работоспособности:
<b>UΛU</b><sup>-1</sup> = ( √5 )<sup>-1</sup> [ Φ 1-Φ ] . [ Φ 0 ] . [ 1 Φ-1 ]
[ 1 1 ] [ 0 1-Φ ] [ -1 Φ ]
let Ψ = 1-Φ, the other eigenvalue
as Φ is a root of λ²-λ-1=0
so -ΨΦ = Φ²-Φ = 1
and Ψ+Φ = 1
<b>UΛU</b><sup>-1</sup> = ( √5 )<sup>-1</sup> [ Φ Ψ ] . [ Φ 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψ ] [ -1 Φ ]
= ( √5 )<sup>-1</sup> [ Φ Ψ ] . [ Φ -ΨΦ ]
[ 1 1 ] [ -Ψ ΨΦ ]
= ( √5 )<sup>-1</sup> [ Φ Ψ ] . [ Φ 1 ]
[ 1 1 ] [ -Ψ -1 ]
= ( √5 )<sup>-1</sup> [ Φ²-Ψ² Φ-Ψ ]
[ Φ-Ψ 0 ]
= [ Φ+Ψ 1 ]
[ 1 0 ]
= [ 1 1 ]
[ 1 0 ]
= <b>M</b>
Итак, проверка работоспособности выполняется.
Теперь у нас есть все, что нам нужно рассчитать M n 1,2 :
<b>M</b><sup><i>n</i></sup> = <b>U</b><b>Λ</b><sup><i>n</i></sup><b>U</b><sup>-1</sup>
= ( √5 )<sup>-1</sup> [ Φ Ψ ] . [ Φ<sup><i>n</i></sup> 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψ<sup><i>n</i></sup> ] [ -1 Φ ]
= ( √5 )<sup>-1</sup> [ Φ Ψ ] . [ Φ<sup><i>n</i></sup> -ΨΦ<sup><i>n</i></sup> ]
[ 1 1 ] [ -Ψ<sup><i>n</i></sup> Ψ<sup><i>n</i></sup>Φ ]
= ( √5 )<sup>-1</sup> [ Φ Ψ ] . [ Φ<sup><i>n</i></sup> Φ<sup><i>n</i>-1</sup> ]
[ 1 1 ] [ -Ψ<sup><i>n</i></sup> -Ψ<sup><i>n</i>-1</sup> ] as ΨΦ = -1
= ( √5 )<sup>-1</sup> [ Φ<sup><i>n</i>+1</sup>-Ψ<sup><i>n</i>+1</sup> Φ<sup><i>n</i></sup>-Ψ<sup><i>n</i></sup> ]
[ Φ<sup><i>n</i></sup>-Ψ<sup><i>n</i></sup> Φ<sup><i>n</i>-1</sup>-Ψ<sup><i>n</i>-1</sup> ]
так
<i>fib</i>(<i>n</i>) = <b>M</b><sup><i>n</i></sup><sub>1,2</sub>
= ( Φ<sup><i>n</i></sup> - (1-Φ)<sup><i>n</i></sup> ) / √5
Что согласуется с формулой, приведенной в другом месте.
Вы можете вывести его из рекуррентного соотношения, но в инженерных вычислениях и симуляции вычисление собственных значений и собственных векторов больших матриц является важным видом деятельности, так как оно обеспечивает устойчивость и гармоничность систем уравнений, а также позволяет поднимать матрицы до высоких державы эффективно.