My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Thanks Tree1Thanks
  • 1 Post By romsek
Reply
 
LinkBack Thread Tools Display Modes
February 11th, 2018, 02:09 PM   #1
Senior Member
 
Joined: Jan 2017
From: Toronto

Posts: 190
Thanks: 2

Using Eigen Values and Vectors for computing complex arithmetic series

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, .... In general, $\displaystyle F_{k+2} = F_{k+1} + F_{k} $.

Here is some background info, we derive the following matrix for computing $\displaystyle F_{100} $:

$\displaystyle
\mathbf{A} =
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
$
$\displaystyle
\begin{bmatrix}
F_{k+2} \\
F_{k+1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{k}
\begin{bmatrix}
F_{k+1} \\
F_{k}
\end{bmatrix}
$

Using EigenValues, EigenVector matrix(S) and Diagonal matrix(D), we can compute the $\displaystyle F_{100}$.

$\displaystyle
\mathbf{A}^{k} = \mathbf{S} \mathbf{D}^{k} \mathbf{S}^{-1}
$

$\displaystyle
\begin{bmatrix}
F_{100} \\
F_{99}
\end{bmatrix}
=
\mathbf{S}
\mathbf{D}^{99}
\mathbf{S}^{-1}
\begin{bmatrix}
F_{2} \\
F_{1}
\end{bmatrix}
$

I have been using this technique to solve a number of standard arthmetric series and geometric series easily. Then I challenged myself and scouted online for some interesting recursive series. I stumbled the following:

Hofstadter's Q-Sequence

$\displaystyle
Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)) \\
Q(1) = Q(2) = 1 \\
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, ....
$

I have been working on this series for a couple of hours without any luck. Would anyone able to figure this out by using the same technique? Is it even possible to solve this problem with this technique alone?

Last edited by zollen; February 11th, 2018 at 02:12 PM.
zollen is offline  
 
February 11th, 2018, 08:10 PM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,100
Thanks: 1093

the sequence relies on the non-linear function $Q()$ and so you're not going to be able to generate this via a set of linear transformations.
Thanks from zollen
romsek is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
arithmetic, complex, computing, eigen, series, values, vectors



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Eigen values for nxn matrix didierB Abstract Algebra 2 January 13th, 2013 04:29 PM
QR factorization- Eigen values atee Linear Algebra 1 February 11th, 2012 03:01 PM
Computing values guru123 Algebra 0 November 17th, 2011 08:11 AM
Calculating Eigen Values error Singularity Linear Algebra 2 April 18th, 2010 01:49 PM
Interval Arithmetic and Reliable Computing YDVIPER Computer Science 1 December 10th, 2007 05:14 AM





Copyright © 2018 My Math Forum. All rights reserved.