Aproximação racional de raízes

No artigo Aproximação racional da raiz quadrada expus um vídeo que elaborei cujo propósito consiste na descrição de um processo que permite calcular rapidamente um valor aproximado de uma raiz quadrada. Podemos encontrar os detalhes e a justificação dos procedimentos em Uma aproximação racional da raiz quadrada.

De uma maneira resumida, começamos por considerar a iteração mútua das médias aritmética e harmónica da forma

\left\lbrace  \begin{matrix}  a_{n+1}=\frac{a_n+b_n}{2}\\  b_{n+1}=\frac{2a_nb_n}{a_n+b_n}  \end{matrix}  \right.

Agora, vamos estudar uma iteração mais geral, começando com o conjunto de p sucessões de números não negativos a_{n}^{(k)} onde k=1,...,p. Fazemos então

a_{n+1}^{(k)}=\frac{\binom{p}{k-1}}{\binom{p}{k}}\frac{\sigma_k\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)}{\sigma_{k-1}\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)}

onde \sigma_k correspondem às funções simétricas elementares. Em particular,

a_{n+1}^{(1)}=\frac{a_{n}^{(1)}+a_{n}^{(2)}+\cdots+a_{n}^{(p)}}{p}

Se fizermos

E_k\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)=\frac{\sigma_k\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)}{\binom{p}{k}}

as iterações escrever-se-ão como

a_{n+1}^{(k)}=\frac{E_k\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)}{E_{k-1}\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)}

Utilizamos ainda a abreviação E_k\left(a_n^{(1)},a_n^{(2)},\cdots a_n^{(p)} \right)=E_k. De acordo com as desigualdades de Newton temos

\frac{E_{k+1}}{E_k}\le\frac{E_k}{E_{k-1}}

isto é, a_{n+1}^{(1)}\ge a_{n+1}^{(2)}\ge\cdots\ge a_{n+1}^{(p)}. Se partirmos de um conjunto de p números, x_1, x_2, …, x_p e definirmos

a_1^{(k)}=\frac{E_k\left(x_1,x_2,\cdots,x_p\right)}{E_k\left(x_1,x_2,\cdots,x_p\right)}

vemos que a_{n+1}^{(k)}\in\left\lbrack a_n^{(1)},a_n^{(p)}\right\rbrack para todo o k. Observamos ainda que as desigualdades de Maclaurin permitem concluir que \sqrt[p]{x_1x_2\cdots x_p}\in\left\lbrack a_1^{(1)},a_1^{(p)}\right\rbrack se todos os x_i forem positivos.

Ora, a_{n}^{(k)}\le a_1^{(1)} para todos os valores de k entre 1 e p. Então

\frac{\sum_{k=1}^p a_n^{(k)}}{p}-a_n^{(p)}=\frac{\sum_{k=1}^{p-1} \left(a_n^{(k)}-a_n^{(p)}\right)}{p}\le \frac{\sum_{k=1}^{p-1} \left(a_n^{(1)}-a_n^{(p)}\right)}{p}=\frac{p-1}{p} \left(a_n^{(1)}-a_n^{(p)}\right)

e também

a_{n+1}^{(k)}-a_n^{(p)}\le a_{n+1}^{(1)}-a_n^{(p)}\le \frac{p-1}{p} \left(a_n^{(1)}-a_n^{(p)}\right)

Por outro lado, temos

a_n^{(1)}-\frac{E_p}{E_{p-1}}=  \frac{\sum_{k=2}^p \left\lbrack{\left(a_n^{(1)}-a_n^{(k)}\right)a_n^{(1)}\prod_{i=2\\ i\ne k}{a_n^{(i)}}}\right\rbrack}{\sum_{k=1}^p{\prod_{i=1\\ i\ne k}{a_n^{(i)}}}}\le\frac{a_n^{(1)}\sum_{k=2}^p\prod_{i=2\\ i\ne k}{a_n^{(i)}}}{\sum_{k=1}^p\prod_{i=1\\ i\ne k}{a_n^{(i)}}}\left(a_n^{(1)}-a_n^{(p)}\right)=\left(1-\frac{\prod_{i=2\\ i\ne k}{a_n^{(i)}}}{\sum_{k=1}^p\prod_{i=1\\ i\ne k}{a_n^{(i)}}}\right)\left(a_n^{(1)}-a_n^{(p)}\right)

Se considerarmos que todos os a_n^{(k)} são positivos, temos, devido às desigualdades desenvolvidas anteriormente,

1-\frac{\prod_{i=2\\ i\ne k}{a_n^{(i)}}}{\sum_{k=1}^p\prod_{i=1\\ i\ne k}{a_n^{(i)}}}\le 1-\frac{1}{p}=\frac{p-1}{p}

e também

a_n^{(1)}-a_{n+1}^{(k)}\le a_n^{(1)}-a_{n+1}^{(k)}\le \frac{p-1}{p}\left(a_n^{(1)}-a_n^{(p)}\right)

Porém, a_n^{(1)}=a_n^{(p)}+\left(a_n^{(1)}-a_n^{(p)}\right). A desigualdade anterior passa-se a escrever, uma vez que a_n^{(1)}\ge a_n^{(p)}, como

a_{n+1}^{(k)}-a_n^{(p)}\ge \frac{1}{p} \left(a_n^{(1)}-a_n^{(p)}\right)

isto é, a_{n+1}^{(k)}\in\left\lbrack a_n^{(p)}+\frac{1}{p}\Delta, a_n^{(p)}+\frac{p-1}{p}\Delta\right\rbrack onde \Delta =a_n^{(1)}-a_n^{(p)}. Vemos, portanto, que a iteração apresentada satisfaz a condição de Lipschitz de onde podemos concluir a sua convergência. Facilmente concluímos também que todas elas convergem para um mesmo limite.

Facilmente verificamos que

\prod_{k=1}^p a_{n}^{(k)}=\prod_{k=1}^p a_{n+1}^{(k)}

e portanto, sendo l o limite para o qual convergem as sucessões,

l^p=\prod_{k=1}^p a_{1}^{(k)}=\prod_{k=1}^p x_k

ou

l=\sqrt[p]{x_1x_2\cdots x_p}

O caso p=2 foi tratado num outro sítio. Aqui vamo-nos centrar no caso p=3. Sejam então x_1, x_2 e x_3 três números não negativos. Definimos as sucessões A_n, B_n e C_n do seguinte modo. Em primeiro lugar, fazemos

\left\lbrace\begin{matrix}  A_1=\frac{x_1+x_2+x_3}{3}\\  B_1=\frac{x_1x_2+x_1x_3+x_2x_3}{x_1+x_2+x_3}\\  C_1=\frac{3x_1x_2x_3}{x_1x_2+x_1x_3+x_2x_3}  \end{matrix}  \right.

e, sem segundo, completamos com a recorrência

\left\lbrace\begin{matrix}  A_{n+1}=\frac{A_n+B_n+C_n}{3}\\  B_{n+1}=\frac{A_nB_n+A_nC_n+B_nC_n}{A_n+B_n+C_n}\\  C_{n+1}=\frac{3A_nB_nC_n}{A_nB_n+A_nC_n+B_nC_n}  \end{matrix}  \right.

Se fizermos x_1=t, x_2=1 e x_3=1, onde t\ge 0, facilmente constatamos que é possível escrever

\left\lbrace\begin{matrix}  A_{n}=\frac{p_n(t)}{q_n(t)}\\  B_{n}=\frac{r_n(t)}{p_n(t)}\\  C_{n}=t\frac{q_n(t)}{r_n(t)}  \end{matrix}  \right.

sendo p_n(t), q_n(t) e r_n(t) polinómios. Também,

\left\lbrace\begin{matrix}  p_1(t)=t+2\\  q_1(t)=3\\  r_1(t)=2t+1  \end{matrix}  \right.

Da expressão de recorrência para as sucessões consideradas vem

\left\lbrace\begin{matrix}  p_{n+1}(t)=p_n^2(t)r_n(t)+r_n^2(t)q_n(t)+tq_n^2(t)p_n(t)\\  q_{n+1}(t)=3p_n(t)q_n(t)r_n(t)\\  r_{n+1}(t)=r_n^2p_n+t\left(p_n^2q_n+q_n^2r_n\right)  \end{matrix}  \right.

Por exemplo, para t=2 temos

n p_n q_n r_n
1 4 3 5
2 227 180 286
3 44170174 35057880 55650932
4 325725522044918661545552 258528518173489924451520 410388441712389573931936

Concluímos as aproximações, para n=2,

\left\lbrace\begin{matrix}  A_{2}=\frac{227}{180}\\  B_{2}=\frac{286}{227}\\  C_{2}=\frac{360}{286}  \end{matrix}  \right.

Resta observar que, para n=4, as aproximações permitem calcular a raiz cúbica de 2 com uma precisão na ordem das vinte casas decimais.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática com as etiquetas , , , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s