Artigos

11.1: A- Jacobianos, Inversos de Matrizes e Valores Próprios


Neste apêndice, coletamos alguns resultados sobre Jacobianos e inversos e autovalores de matrizes (2 vezes 2 ) que são usadas repetidamente no material.

Primeiro, consideramos a expansão de Taylor de uma função de valor vetorial de duas variáveis, denotadas da seguinte forma:

[H (x, y) = begin {pmatriz} {f (x, y)} {g (x, y)} end {pmatriz}, (x, y) in mathbb {R} ^ 2, label {A.1} ]

Mais precisamente, precisaremos expandir Taylor tais funções por meio de segunda ordem:

[H (x_ {0} + h, y_ {0} + k) = H (x_ {0}, y_ {0}) + DH (x_ {0}, y_ {0}) begin {pmatriz} { h} {k} end {pmatriz} + mathcal {O} (2). label {A.2} ]

A expansão de Taylor de uma função de valor escalar de uma variável deve ser familiar para a maioria dos alunos neste nível. Possivelmente, há menos familiaridade com a expansão de Taylor de uma função de valor vetorial de uma variável vetorial. No entanto, para calcular isso, nós apenas Taylor expandimos cada componente da função (que é uma função de valor escalar de uma variável vetorial) em cada variável, mantendo a outra variável fixa para a expansão nessa variável particular, e então reunimos os resultados para cada componente em forma de matriz.

Realizar este procedimento para o componente (f (x, y) ) da Equação ref {A.1} dá:

[ begin {align} f (x_ {0} + h, y_ {0} + k) & = f (x_ {0}, y_ {0} + k) + frac { partial f} { partial x} (x_ {0}, y_ {0} + k) h + mathcal {O} (h ^ 2) [4pt] & = f (x_ {0}, y_ {0}) + frac { parcial f} { parcial y} (x_ {0}, y_ {0}) k + mathcal {O} (k ^ 2) + frac { parcial f} { parcial x} (x_ {0}, y_ {0}) h + mathcal {O} (hk) + mathcal {O} (h ^ 2). label {A.3} end {align} ]

O mesmo procedimento pode ser aplicado a (g (x, y) ). Recombinar os termos de volta na expressão vetorial para a Equação ref {A.1} dá:

[H (x_ {0} + h, y_ {0} + k) = begin {pmatriz} {f (x_ {0}, y_ {0})} {g (x_ {0}, y_ { 0})} end {pmatriz} + begin {pmatrix} { frac { partial f} { partial x} (x_ {0}, y_ {0})} & { frac { partial f} { parcial y} (x_ {0}, y_ {0})} { frac { parcial g} { parcial x} (x_ {0}, y_ {0})} & { frac { parcial g} { parcial y} (x_ {0}, y_ {0})} end {pmatriz} begin {pmatriz} {h} {k} end {pmatriz} + mathcal {O} (2 ), label {A.4} ]

Portanto, o Jacobiano da Equação ref {A.1} em ((x_ {0}, y_ {0}) ) é:

[ begin {pmatrix} { frac { partial f} { partial x} (x_ {0}, y_ {0})} & { frac { partial f} { partial y} (x_ {0 }, y_ {0})} { frac { parcial g} { parcial x} (x_ {0}, y_ {0})} & { frac { parcial g} { parcial y} ( x_ {0}, y_ {0})} end {pmatrix}, label {A.5} ]

que é uma matriz (2 vezes 2 ) de números reais.

Precisaremos calcular o inverso dessas matrizes, bem como seus autovalores.

Denotamos uma matriz geral (2 vezes 2 ) de números reais:

[A = begin {pmatrix} {a} & {b} {c} & {d} end {pmatrix}, a, b, c, d in mathbb {R}. label {A.6} ]

É fácil verificar que o inverso de A é dado por:

[A ^ {- 1} = frac {1} {ad-bc} begin {pmatrix} {d} & {- b} {-c} & {a} end {pmatrix}. label {A.7} ]

Deixe ( mathbb {I} ) denotar a matriz de identidade (2 vezes 2 ). Então, os autovalores de A são as soluções da equação característica:

[det (A - lambda mathbb {I}) = 0. label {A.8} ]

onde "det" é a notação para o determinante da matriz. Esta é uma equação quadrática em ( lambda ) que tem duas soluções:

[ lambda_ {1,2} = frac {tr A} {2} pm frac {1} {2} sqrt {(tr A) ^ 2-4det A}, label {A.9} ]

onde usamos a notação:

(tr A equiv trace A = a + d ), (det A equiv determinante A = ad-bc ).


11.1: A- Jacobianos, Inversos de Matrizes e Valores Próprios

A matriz identidade atua como 1 na álgebra matricial. Por exemplo, [latex] AI = IA = A [/ latex].

Uma matriz que tem um inverso multiplicativo tem as propriedades

Uma nota geral: a matriz de identidade e o inverso multiplicativo

O matriz de identidade, [látex]_[/ latex], é uma matriz quadrada contendo uns na diagonal principal e zeros em todas as outras partes.

Se [latex] A [/ latex] é uma matriz [latex] n times n [/ latex] e [latex] B [/ latex] é uma matriz [latex] n times n [/ latex] tal que [latex ] AB = BA =_[/ latex], então [latex] B = ^ <-1> [/ latex], o inverso multiplicativo de uma matriz [latex] A [/ latex].

Exemplo 1: Mostrando que a Matriz de Identidade age como um 1

Matriz dada UMA, mostre que [látex] AI = IA = A [/ látex].

Solução

Use a multiplicação da matriz para mostrar que o produto de [latex] A [/ latex] e a identidade é igual ao produto da identidade e UMA.

Como: Dadas duas matrizes, mostre que uma é o inverso multiplicativo da outra.

  1. Dada matriz [latex] A [/ latex] de ordem [latex] n times n [/ latex] e matriz [latex] B [/ latex] de ordem [latex] n times n [/ latex] multiplicação [latex] AB [/ latex].
  2. Se [latex] AB = I [/ latex], encontre o produto [latex] BA [/ latex]. Se [latex] BA = I [/ latex], então [latex] B = ^ <-1> [/ latex] e [latex] A =^ <-1> [/ latex].

Exemplo 2: Mostrando essa matriz UMA É o inverso multiplicativo da matriz B

Mostre que as matrizes fornecidas são inversas multiplicativas umas das outras.

Solução

Multiplique [latex] AB [/ latex] e [latex] BA [/ latex]. Se ambos os produtos igualam a identidade, então as duas matrizes são inversas uma da outra.

[latex] A [/ latex] e [latex] B [/ latex] são inversos um do outro.

Experimente 1

Mostre que as duas matrizes a seguir são inversas uma da outra.


$ A $ singular $ iff det (A) = 0 iff det (A-0 cdot I) = 0 iff 0 $ é o autovalor de $ A $.

Observe que, o determinante de $ n vezes n $ matriz $ A $ pode ser calculado usando os valores próprios como

que é o produto dos valores próprios.

Sabemos que in lambda (A) $ iff existe alguma solução diferente de zero para a equação do vetor próprio $ Ax = lambda x = 0 cdot x = 0 $. Assim, $ é um valor próprio iff $ existe b in mathrm(A) $ com $ b neq 0 $. Mas desde $ mathrm(A) neq <0 > $ concluímos que $ A $ deve ser singular.

Supondo que por & ldquosingular & rdquo, você quer dizer uma matriz quadrada que não é invertível:

Lema: Se $ A $ é invertível e $ lambda $ é um autovalor de $ A $, então $ frac <1> < lambda> $ é um autovalor de $ A ^ <-1> $.

Seja $ x $ o autovetor de $ A $ correspondente ao autovalor $ lambda $. Por definição, $ Ax = lambda x $. Multiplique à esquerda por $ A ^ <-1> $, resultando em $ A ^ <-1> Ax = A ^ <-1> lambda x $. O LHS é igual a $ x $ ($ A ^ <-1> A = I $ por definição) e o RHS é igual a $ lambda A ^ <-1> x $ (porque matriz & vezes escalar comuta), então $ x = lambda A ^ <-1> x $. Divida ambos os lados por $ lambda $, dando $ frac <1> < lambda> x = A ^ <-1> x $. Por definição, $ frac <1> < lambda> $ é, portanto, um autovalor de $ A ^ <-1> $.

Portanto, se $ fosse um autovalor de $ A $, então $ frac <1> <0> $ seria um autovalor de $ A ^ <-1> $. Mas $ frac <1> <0> $ não é um número, então $ A ^ <-1> $ também não pode existir.


SIAM Journal on Matrix Analysis and Applications

Para uma função com valor de matriz $ n times n $ $ L (< boldsymbol rho>, lambda) $, onde $ < boldsymbol rho> $ é um vetor de parâmetros independentes e $ lambda $ é um parâmetro próprio , o problema do autovalor-autovetor tem a forma $ L (< boldsymbol rho>, lambda (< boldsymbol rho>) < bf x> (< boldsymbol rho>)) = < bf 0> $ . Valores reais ou complexos para $ < boldsymbol rho> $ e $ lambda $ são permitidos, e eu presume-se que dependa analiticamente dessas variáveis. Em particular, a dependência não linear de $ lambda $ é a principal preocupação. Partindo do pressuposto de que o próprio problema do autovalor-autovetor pode ser resolvido de forma satisfatória, é feito um estudo das derivadas (sensibilidades) de $ lambda $ e $ < bf x> $ em relação a $ < boldsymbol rho> $. A análise é feita da existência de derivadas, do efeito de estratégias de normalização e da solubilidade e condição das equações matriciais com bordas que surgem naturalmente neste contexto. As implicações para vários problemas clássicos de autovalor $ L (< boldsymbol rho>, lambda) = A (< boldsymbol rho>) - lambda I $ são esclarecidas.


2 respostas 2

Não, uma matriz não pode ter mais de uma inversa, mas não pode ter nenhuma inversa, matematicamente.

Mas todos os cálculos em um computador são realizados com representações de ponto flutuante finito e vários tipos de imprecisões que podem ocorrer em cada etapa do cálculo.

O resultado da inversão numérica de uma matriz depende de quão "bem condicionada" a matriz é. Mesmo que uma matriz possa ser invertida, se não estiver bem condicionada, pequenas mudanças na entrada podem causar grandes mudanças na saída. Como os valores em uma matriz são representados por representações de ponto flutuante finito, apenas representações internas ligeiramente diferentes podem causar grandes diferenças. Além disso, como todos os cálculos são realizados por representações de ponto flutuante finito, os detalhes do algoritmo usado podem causar diferenças com uma matriz mal condicionada.

Resposta um pouco mais detalhada: Quando a matriz não está bem condicionada, isso significa que ela tem alguns autovalores muito pequenos. Vamos usar a decomposição de valores singulares, se sua matriz for X = L @ S @ R.T, então o inverso é Xi = R @ np.sqrt (S) @ L.T. Agora a parte do meio está invertendo os autovalores e se houver alguns muito pequenos, o erro de ponto flutuante pode ter uma grande diferença em seu inverso e, portanto, a diferença que você está vendo ali.

Mas isso importa? Não, se sua matriz não estiver bem condicionada, então o inverso que você está calculando não é confiável. Você pode testar isso multiplicando-o por sua matriz original e ver que nem todos os elementos estão próximos da matriz de identidade.

Qual é a solução? 1. Use um pré-condicionador 2. Se você ver uma grande mudança nos autovalores de sua matriz original, simplesmente jogue fora esses autovalores e autovetores sem importância, reconstrua sua matriz e então seu inverso deve ser o mesmo, independentemente da plataforma / pacote / sistema operacional que você estão usando. Observe que a primeira abordagem é basicamente fazer a mesma coisa que a segunda, apenas diferentes etapas matemáticas.


Diagonalização da matriz 3x3

Código C ++ simples que encontra um quatérnio que diagonaliza uma matriz 3x3:

Diagonalizar um 3x3 simétrico tem várias aplicações úteis, como diagonalizar tensores de inércia, ajustar OBBs, encontrar eixos principais, etc. As entradas diagonais da matriz diagonalizada são os autovalores e o quaternion representa os autovetores em que as linhas da matriz correspondente são os autovetores . Observe que essas seriam as colunas da matriz para vocês, pessoal da coluna principal. Nota: O código real no meu site github pode usar algumas convenções diferentes (estilo de nomenclatura e agora na coluna principal).

Este código é mantido simples para que seja fácil de pegar e incorporar em sua própria biblioteca de matemática 3D ou aplicativo de jogo. Renomeie os tipos vetoriais, matriciais e quat como achar necessário. Esteja ciente de qualquer armazenamento de matriz (linha vs coluna) e convenções de ordem de multiplicação que você possa estar usando. O código assume as convenções de linha principal e D3D da linguagem C para a ordenação dos elementos da matriz (por exemplo, v_world = v_local * M). Você deve ter notado que os comentários escrevem D = Q * M * Q ^ T, enquanto um livro de álgebra linear centrado em colunas provavelmente escreveria D = Q ^ T * M * Q em vez disso. A associação do quatérnio com matrizes e multiplicação é a mesma ordem que literalmente todo mundo usa. Até onde sei, isso inclui a implementação do quatérnio do D3DX, embora sua ordem de matriz do D3D oposta, o que significaria: (Qa * Qb) .AsMatrix () == Qb.AsMatrix () * Qa.AsMatrix (). De qualquer forma, a função pode ser facilmente modificada para se adequar à sua preferência caso seja diferente.

Quando você chama a rotina para uma matriz M e obtém um quatérnio q cuja matriz correspondente é Q e então calcula D = Q * M * Q ^ T, você provavelmente notará que os elementos fora da diagonal de D não são exatamente zero. Os internos do algoritmo são todos flutuantes de 32 bits. Alterar isso para o dobro pode melhorar o resultado. Mesmo assim, o quaternion resultante será representado com precisão finita (32 bits xyzw). Para o loop principal de funções, eu apenas codifiquei um limite de iteração de 24. Não há uma boa razão para esse número. Jogando dezenas de matrizes simétricas aleatórias na função, não o vi usar mais de 7 antes de satisfazer uma das condições de saída. Observe que as entradas aleatórias foram inicializadas com (float) rand () / (float) rand (). Pelo que vi, os elementos fora da diagonal sempre foram muitas ordens de magnitude menores do que o maior elemento da diagonal e menores do que a menor diagonal. Mais testes de cobertura em casos mais extremos podem ser úteis.


Algoritmos Quânticos¶

Nesta seção, descrevemos os algoritmos quânticos atualmente disponíveis no Aqua.

Aqua requer a associação de um dispositivo ou simulador quântico a qualquer experimento que use um algoritmo quântico. Isso é feito configurando a seção & quotbackend & quot do experimento a ser executado. Consulte a documentação no Arquivo de entrada para obter mais detalhes.

Variational Quantum Eigensolver (VQE) ¶

VQE é um algoritmo híbrido que usa a abordagem variacional e intercala cálculos quânticos e clássicos para encontrar o autovalor mínimo do hamiltoniano (H ) de um determinado sistema. Uma instância de VQE requer a definição de dois subcomponentes algorítmicos: uma função de teste da biblioteca Variational Forms do Aqua e um otimizador clássico da biblioteca Optimizers do Aqua. Um estado inicial da biblioteca de Estados iniciais do Aqua também pode ser fornecido para definir o estado inicial para a função de teste.

Consulte a documentação de formas variacionais, otimizadores e estados iniciais para obter mais detalhes.

Além disso, o VQE pode ser configurado com os seguintes parâmetros:

Um valor str indicando o modo usado pela classe Operator para o cálculo:

Se nenhum valor para operator_mode for especificado, o padrão será & quotmatrix & quot.

O ponto inicial para a busca do autovalor mínimo:

Uma lista opcional de valores flutuantes pode ser fornecida como o ponto de partida para a pesquisa do valor próprio mínimo. Esse recurso é particularmente útil quando há razões para acreditar que o ponto de solução está próximo a um ponto específico, que pode então ser fornecido como o ponto inicial preferido. Por exemplo, ao construir o perfil de dissociação de uma molécula, é provável que usar a solução ideal computada anterior como o ponto inicial para a próxima distância interatômica irá reduzir o número de iterações necessárias para o algoritmo variacional convergir. Aqua fornece um tutorial inicial detalhando este caso de uso.

O comprimento do valor da lista de pontos_inicial deve corresponder ao número de parâmetros esperados pela forma variacional que está sendo usada. Se o usuário não fornecer um ponto inicial preferencial, o VQE procurará na forma variacional um valor preferencial. Se a forma variacional retornar Nenhum, um ponto aleatório será gerado dentro dos limites do parâmetro definidos, conforme acima. Se a forma variacional fornecer Nenhum como o limite inferior, então o VQE irá padronizar para (- 2 pi ) similarmente, se a forma variacional retornar Nenhum como o limite superior, o valor padrão será (2 pi ) .

Ao se referir ao VQE declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é VQE.

No Aqua, o VQE suporta os problemas de energia e alimentação.

Algoritmo de Otimização Aproximada Quântica (QAOA) ¶

QAOA é um algoritmo bem conhecido para encontrar soluções aproximadas para problemas de otimização combinatória. A implementação QAOA no Aqua usa diretamente o VQE para sua estrutura geral de otimização híbrida. No entanto, ao contrário do VQE, que pode ser configurado com formas variacionais arbitrárias, QAOA usa sua própria forma variacional ajustada, que compreende (p ) rotações globais parametrizadas (x ) e (p ) diferentes parametrizações do problema hamiltonian. Como resultado, ao contrário do VQE, QAOA não precisa ter uma forma variacional especificada como um parâmetro de entrada e é configurado principalmente por um único parâmetro inteiro, p, que dita a profundidade da forma variacional e, portanto, afeta a qualidade de aproximação. Um estado inicial da biblioteca de Estados iniciais do Aqua também pode ser fornecido.

Consulte a documentação sobre otimizadores e estados iniciais para obter mais detalhes.

Em resumo, o QAOA pode ser configurado com os seguintes parâmetros:

Um valor str indicando o modo usado pela classe Operator para o cálculo:

Se nenhum valor para operator_mode for especificado, o padrão será & quotmatrix & quot.

Um valor int positivo configurando a profundidade da forma variacional de QAOA, conforme discutido acima:

Deve ser um valor interno positivo. O padrão é 1.

O ponto inicial para a busca do autovalor mínimo:

Uma lista opcional de valores flutuantes de (2p ) pode ser fornecida como os parâmetros beta e gama iniciais (como identificados de forma idêntica no documento QAOA original) para a forma variacional de QAOA. Se essa lista não for fornecida, o QAOA simplesmente começará com o vetor zero.

Um operador opcional pode ser fornecido como um hamiltoniano de misturador personalizado. Isso permite, como discutido neste artigo para o recozimento quântico, e neste artigo para QAOA, executar problemas de otimização restrita onde o misturador restringe a evolução para um subespaço viável do espaço de Hilbert completo.

Semelhante ao VQE, um otimizador também pode ser especificado.

Ao se referir a QAOA declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é QAOA.Variational.

No Aqua, o QAOA apóia o problema de criação.

Evolução do Hamiltoniano (EOH) ¶

EOH fornece os blocos de construção de nível inferior para simular sistemas quânticos universais. Para qualquer sistema quântico dado que pode ser decomposto em interações locais (por exemplo, um hamiltoniano global como a soma ponderada de vários operadores de spin de Pauli), as interações locais podem então ser usadas para aproximar o sistema quântico global via, por exemplo, o método de Lloyd ou decomposição Trotter-Suzuki.

Este algoritmo suporta apenas o simulador de vetor de estado local.

O EOH pode ser configurado com as seguintes configurações de parâmetro:

Um valor flutuante é esperado. O valor mínimo é 0,0. O valor padrão é 1.0.

O modo de evolução da computação:

Dois valores str são permitidos: & quotmatrix & quot ou & quotcircuit & quot, com & quotcircuit & quot sendo o padrão.

O número de intervalos de tempo:

Este deve ser um valor interno não negativo. O padrão é 1.

Dois valores str são permitidos: & quottrotter & quot (método de Lloyd) ou & quotsuzuki & quot (para expansão Trotter-Suzuki), com & quottrotter & quot sendo o padrão.

Este parâmetro define a ordem de expansão do Trotter-Suzuki. Um valor int positivo é esperado. O valor padrão é 2.

Ao se referir ao EOH declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é EOH.

No Aqua, o EOH dá suporte ao problema eoh.

Estimativa de fase quântica (QPE) ¶

QPE (às vezes também abreviado como PEA, para Algoritmo de estimativa de fase), leva dois registros quânticos, ao controle e alvo, onde o controle consiste em vários qubits inicialmente colocados em sobreposição uniforme e o alvo é um conjunto de qubits preparado em um estado próprio (ou, muitas vezes, uma estimativa do estado próprio) do operador unitário de um sistema quântico. O QPE então evolui o alvo sob o controle usando Evolução do Hamiltoniano (EOH) no operador unitário. A informação do autovalor correspondente é então chutado de volta nas fases do registro de controle, que pode então ser deconvoluído por uma Transformada Quântica Inversa de Fourier (IQFT), e medido para leitura em formato decimal binário. O QPE também requer uma estimativa razoavelmente boa da função de onda própria para iniciar o processo. Por exemplo, ao estimar as energias moleculares do solo, o método Hartree-Fock pode ser usado para fornecer tais funções de eigen wave de teste.

Consulte a documentação sobre transformadas quânticas de Fourier e estados iniciais para obter mais detalhes.

Além de exigir um IQFT e um estado inicial como parte de sua configuração, o QPE também expõe as seguintes configurações de parâmetro:

O número de intervalos de tempo:

Este deve ser um valor interno não negativo. O valor padrão é 1.

Dois valores str são permitidos: & quottrotter & quot (método de Lloyd) ou & quotsuzuki & quot (para expansão Trotter-Suzuki), com & quottrotter & quot sendo o padrão.

Este parâmetro define a ordem de expansão do Trotter-Suzuki. Um valor int positivo é esperado. O valor padrão é 2.

Este parâmetro define o número de qubits auxiliares a serem usados ​​pelo QPE. Um valor int positivo é esperado. O valor padrão é 1.

Ao se referir ao QPE declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é QPE.

No Aqua, o QPE apóia o problema de energia.

Estimativa de fase quântica iterativa (IQPE) ¶

O IQPE, como o próprio nome sugere, calcula iterativamente a fase de modo a exigir menos qubits. Leva o mesmo conjunto de parâmetros como QPE, exceto para o número de qubits auxiliares num_ancillae, que é substituído por num_iterations (um int positivo, também padronizado como 1), e pelo fato de que uma Transformada Quântica Inversa de Fourier (IQFT) é não usado para IQPE.

Para obter mais detalhes, consulte arXiv: quant-ph / 0610214.

Ao se referir ao IQPE declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é IQPE.

No Aqua, o IQPE apóia o problema de energia.

Estimativa de amplitude¶

Estimativa de Amplitude é uma derivada de - Quantum Phase Estimation (QPE) aplicada a um determinado operador (A ). (A ) é assumido para operar em (n + 1 ) qubits (mais possíveis qubits auxiliares), onde os (n ) qubits representam a incerteza (na forma de uma distribuição aleatória da biblioteca de Distribuições Aleatórias) e o último qubit, chamado de qubit objetivo, é usado para representar o valor objetivo normalizado como sua amplitude. Em outras palavras, (A ) é construído de tal forma que a probabilidade de medir um '1' no qubit objetivo é igual ao valor de interesse.

Consulte a documentação sobre - Quantum Phase Estimation (QPE) para mais detalhes. Além disso, consulte arXiv: 1806.06893 para obter mais detalhes sobre a estimativa de amplitude, bem como suas aplicações em problemas financeiros.

Além de contar com um componente QPE para construir o circuito Quantum Phase Estimation, a fim de ser construído corretamente, um objeto de algoritmo AmplitudeEstimation espera as seguintes entradas:

O número de qubits de avaliação:

Deve ser um valor interno positivo.

Um objeto CircuitFactory que representa o problema da incerteza, ou seja, o operador (A ) mencionado acima.

O problema opcional unitário:

Um objeto CircuitFactory opcional que representa o problema unitário, que, se não for especificado, será construído automaticamente a partir da a_factory.

O componente da Transformada Quântica Inversa de Fourier:

O componente plugável Inverse Quantum Fourier Transform que deve ser usado para configurar o componente PhaseEstimation. O iqft padrão será usado por padrão se for deixado Nenhum.

Ao se referir à estimativa de amplitude declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é AmplitudeEstimation.

No Aqua, a estimativa de amplitude suporta o problema da incerteza.

Quantum Grover Search¶

A Pesquisa de Grover é um algoritmo quântico bem conhecido para pesquisar através de coleções não estruturadas de registros para alvos específicos com aceleração quadrática em comparação com algoritmos clássicos.

Dado um conjunto (X ) de (N ) elementos (X = ) e uma função booleana (f: X rightarrow <0,1 > ), a meta em um problema de pesquisa não estruturada é encontrar um elemento (x ^ * em X ) tal que (f (x ^ *) = 1 ). A pesquisa não estruturada é frequentemente formulada alternativamente como um problema de pesquisa de banco de dados, no qual, dado um banco de dados, o objetivo é encontrar nele um item que atenda a alguma especificação. A busca é chamada não estruturado porque não há garantias de como o banco de dados é ordenado. Em um banco de dados classificado, por exemplo, pode-se realizar uma pesquisa binária para encontrar um elemento em ( mathbb( log N) ) hora do pior caso. Em vez disso, em um problema de pesquisa não estruturada, não há conhecimento prévio sobre o conteúdo do banco de dados. Com os circuitos clássicos, não há alternativa a não ser realizar um número linear de consultas para encontrar o elemento de destino. Por outro lado, o algoritmo de pesquisa de Grover permite resolver o problema de pesquisa não estruturada em um computador quântico em ( mathcal( sqrt) ) consultas.

Tudo o que é necessário para realizar uma pesquisa é um oráculo de Grover da biblioteca Oracles do Aqua para especificar o critério de pesquisa, que basicamente indica um acerto ou erro para qualquer registro. Mais formalmente, um oráculo (O_f ) é um objeto que implementa uma função booleana (f ) conforme especificado acima. Dada uma entrada (x em X ), (O_f ) implementa (f (x) ). Os detalhes de como (O_f ) funciona não são importantes. O algoritmo de pesquisa de Grover trata o oráculo como uma caixa preta. Atualmente, o Aqua fornece um Oracle de Expressão Lógica e um Oracle de Tabela de Verdade, os quais podem ser usados ​​nas tarefas de pesquisa de Grover. Em particular, a Expressão Lógica Oracle pode tomar como entrada uma instância de problema SAT no formato DIMACS CNF e construir o circuito quântico correspondente, que pode então ser alimentado para o algoritmo de Grover para encontrar uma atribuição satisfatória.

Os oráculos são tratados como componentes plugáveis ​​em pesquisadores do Aqua interessados ​​em contribuir para o Aqua podem projetar e implementar novos oráculos e estender a biblioteca de oráculos do Aqua.

A Pesquisa de Grover por padrão usa superposição uniforme para inicializar seu estado quântico. No entanto, um estado inicial da biblioteca de Estados iniciais do Aqua pode ser fornecido para criar qualquer estado quântico inicial. Isso pode ser útil, por exemplo, se o usuário já tiver algum conhecimento prévio sobre onde o (s) alvo (s) de pesquisa podem estar localizados.

Consulte a documentação Estados iniciais para obter mais detalhes.

Grover também pode ser configurado com as seguintes configurações de parâmetro:

Para o algoritmo de busca convencional de Grover, o parâmetro num_iterations é usado para especificar quantas vezes o sub-circuito de fase de marcação e reflexão é repetido para amplificar a (s) amplitude (s) do (s) alvo (s). Um valor int positivo é esperado. O valor padrão é 1.

Quando executado em modo incremental, a tarefa de pesquisa será realizada em rodadas sucessivas, utilizando circuitos construídos com número incrementalmente maior de iterações para a repetição da amplificação de amplitude até que um alvo seja encontrado ou o número máximo ( log N ) ( (N ) sendo o número total de elementos no conjunto do oráculo usado) de iterações é alcançado. A implementação segue a Seção 4 de Boyer et al. O padrão do sinalizador booleano incremental é False. Quando definido como True, o outro parâmetro num_iterations será ignorado.

Ao se referir a Quantum Grover Search declarativamente dentro do Aqua, seu codinome, pelo qual o Aqua o descobre e carrega dinamicamente, é Grover.

No Aqua, o algoritmo de pesquisa de Grover suporta o problema de pesquisa.

Deutsch-Jozsa¶

O algoritmo Deutsch-Jozsa foi um dos primeiros algoritmos quânticos conhecidos a apresentar uma aceleração exponencial em comparação com um algoritmo clássico determinístico (não probabilístico), dado uma função de oráculo de caixa preta. O algoritmo determina se a função dada (f: <0,1 > ^ n rightarrow <0,1 > ) é constante ou balanceada. Uma função constante mapeia todas as entradas para 0 ou 1, e uma função balanceada mapeia metade de suas entradas para 0 e a outra metade para 1. Qualquer um dos oráculos fornecidos pelo Aqua pode ser usado com o algoritmo Deutsch-Jozsa, desde que o A função booleana implementada pelo oráculo de fato satisfaz a restrição de ser constante ou balanceada. Acima dito, uma instância Truth Table Oracle pode ser mais fácil de construir para atender à restrição, mas uma Expressão Lógica Oracle certamente também pode ser usada.

Ao se referir a Deutsch-Jozsa declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é DeutschJozsa.

No Aqua, o algoritmo Deutsch-Jozsa suporta o problema de avaliação de funções.

Bernstein-Vazirani¶

O algoritmo Bernstein-Vazirani é uma extensão / restrição do algoritmo Deutsch-Jozsa. O objetivo do algoritmo é determinar uma string secreta (s in <0,1 > ^ n ), dada uma função oráculo de caixa preta que mapeia (f: <0,1 > ^ n rightarrow <0,1 > ) de modo que (f (x) = s cdot x ( bmod 2) ).

Ao se referir a Bernstein-Vazirani declarativamente dentro do Aqua, seu codinome, pelo qual o Aqua o descobre e carrega dinamicamente, é BernsteinVazirani.

No Aqua, o algoritmo de Bernstein-Vazirani suporta o problema de hiddenstringfinding.

Simon¶

O algoritmo do Simon encontra um inteiro oculto (s in <0,1 > ^ n ) de um oráculo (f_s ) que satisfaz (f_s (x) = f_s (y) ) se e somente se (y = x oplus s ) para todos (x in <0,1 > ^ n ). Assim, se (s = 0 ldots 0 ), ou seja, a cadeia de bits totalmente zero, então (f_s ) é uma função 1 para 1 (ou permutação). Caso contrário, se (s neq 0 ldots 0 ), então (f_s ) é uma função 2 para 1. Dos oráculos incluídos no Aqua, o Truth Table Oracle deve ser o mais fácil de usar para criar um que possa ser usado com o algoritmo Simon.

Ao se referir a Simon declarativamente dentro do Aqua, seu codinome, pelo qual o Aqua o descobre e carrega dinamicamente, é Simon.

No Aqua, o algoritmo Simon suporta o problema de localização periódica.

Máquina de vetor de suporte quântico (QSVM) ¶

Algoritmos e métodos de classificação para aprendizado de máquina são essenciais para o reconhecimento de padrões e aplicativos de mineração de dados. Técnicas bem conhecidas, como máquinas de vetores de suporte ou redes neurais, floresceram nas últimas duas décadas como resultado dos avanços espetaculares nas capacidades e velocidade computacionais do hardware clássico. Esse avanço no poder do computador possibilitou a aplicação de técnicas desenvolvidas teoricamente em meados do século XX em problemas de classificação que logo se tornaram cada vez mais desafiadores.

Um conceito chave nos métodos de classificação é o de kernel. Os dados normalmente não podem ser separados por um hiperplano em seu espaço original. Uma técnica comum usada para encontrar tal hiperplano consiste em aplicar uma função de transformação não linear aos dados. Esta função é chamada de mapa de recursos, à medida que transforma as características brutas, ou propriedades mensuráveis, do fenômeno ou assunto em estudo. Classificar neste novo espaço de recursos - e, na verdade, também em qualquer outro espaço, incluindo o original bruto - nada mais é do que ver o quão próximos os pontos de dados estão uns dos outros. Isso é o mesmo que calcular o produto interno para cada par de dados no conjunto. Na verdade, não precisamos calcular o mapa de feições não lineares para cada datum, mas apenas o produto interno de cada par de pontos de dados no novo espaço de feições. Esta coleção de produtos internos é chamada de núcleo e é perfeitamente possível ter mapas de características difíceis de calcular, mas cujos kernels não são.

O algoritmo QSVM se aplica a problemas de classificação que requerem um mapa de recursos para o qual computar o kernel não é eficiente classicamente. Isso significa que se espera que os recursos computacionais necessários aumentem exponencialmente com o tamanho do problema. QSVM usa um processador Quantum para resolver este problema por uma estimativa direta do kernel no espaço de recursos. O método usado se enquadra na categoria do que é chamado aprendizagem supervisionada, consistindo em um fase de treinamento (onde o kernel é calculado e os vetores de suporte obtidos) e um fase de teste ou classificação (onde novos dados sem etiqueta são classificados de acordo com a solução encontrada na fase de treinamento).

QSVM pode ser configurado com um parâmetro bool, indicando se deve ou não imprimir informações adicionais quando o algoritmo está em execução:

Ao se referir a QSVM declarativamente dentro do Aqua, seu nome de código, pelo qual o Aqua o descobre e carrega dinamicamente, é QSVM.

No Aqua, o QSVM suporta o problema de classificação.

Variational Quantum Classifier (VQC)¶

Similar to QSVM, the VQC algorithm also applies to classification problems. VQC uses the variational method to solve such problems in a quantum processor. Specifically, it optimizes a parameterized quantum circuit to provide a solution that cleanly separates the data.

VQC can be configured with the following parameters:

The depth of the variational circuit to be optimized:

An integer value greater than or equal to 3 is expected. The default is 3 .

A Boolean indicating whether or not to print additional information when the algorithm is running:

A bool value is expected. The default is False .

When referring to VQC declaratively inside Aqua, its code name , by which Aqua dynamically discovers and loads it, is VQC .

In Aqua, VQC supports the classification problem.

HHL algorithm for solving linear systems (HHL)¶

O HHL algorithm (after the author’s surnames Harrow-Hassidim-Lloyd) is a quantum algorithm to solve systems of linear equations (Aoverrightarrow=overrightarrow) . Using the Quantum Phase Estimation algorithm ( Quantum Phase Estimation (QPE) ), the linear system is transformed into diagonal form in which the matrix (A) is easily invertible. The inversion is achieved by rotating an ancillary qubit by an angle (arcsin< frac>>) around the y-axis where (lambda_mathrm) are the eigenvalues of (A) . After uncomputing the register storing the eigenvalues using the inverse QPE, one measures the ancillary qubit. A measurement of 1 indicates that the matrix inversion succeeded. This leaves the system in a state proportional to the solution vector (|x angle) . In many cases one is not interested in the single vector elements of (|x angle) but only on certain properties. These are accessible by using problem-specific operators. Another use-case is the implementation in a larger quantum program.

When HHL is executed using a dictionary non-hermitian matrices and matrices with dimensions other than (2^) are automatically expanded to hermitian matrices and next higher dimension (2^) , respectively. The returned result of the HHL algorithm for expanded matrices will be truncated.

A Boolean indicating whether or not to truncate matrix and result vector from dimension (2^) to dimension given by orig_size by simply cutting off entries with larger indices. This parameter is set to True if HHL is executed using the dictionary approach and the input does not have dimension (2^) .

A bool value is expected. The default is False .

An integer defining the dimension of the input matrix and vector before expansion to dimension (2^) has been applied. This parameter is needed if truncate_powerdim is set to True and will be automatically set when HHL is executed using the dictionary approach and the input does not have dimension (2^) .

An int value or None is epxected. The defult is None .

A Boolean indicating whether or not to truncate matrix and result vector to half the dimension by simply cutting off entries with other indices after the input matrix was expanded to be hermitian following

where the conjugate transpose of matrix (A) is denoted by (A^mathsf) . The truncation of the result vector is done by simply cutting off entries of the upper half. This parameter is set to True if HHL is executed using the dictionary approach and the input matrix is not hermitian.

A bool value is expected. The default is False .

HHL requires eigenvalue estimation using QPE ( Eigenvalues ), the eigenvalue inversion ( Reciprocals ), and a matrix and initial state as part of its configuration.

When referring to HHL declaratively inside Aqua, its code name , by which Aqua dynamically discovers and loads it, is HHL .

In Aqua, HHL supports the linear_system problem.

Shor’s Factory Algorithm (Shor)¶

Shor’s Factoring algorithm is one of the most well-known quantum algorithms. It takes advantage of Quantum Fourier Transforms circuits and finds the prime factors for input integer (N) in polynomial time. The Shor’s algorithm included in Aqua is adapted from this implementation.

The input integer N (defaulted to 15 if omitted) to be factored is expected to be odd and greater than 2. Even though our implementation is general, its capability will be limited by the capacity of the simulator/hardware. Another input integer a (defaulted to 2 if omitted) can also be supplied, which needs to be a coprime smaller than N .

For more details, please see this implementation and this paper.

When referring to Shor’s algorithm declaratively inside Aqua, its code name , by which Aqua dynamically discovers and loads it, is Shor .

In Aqua, Shor’s algorithm supports the factoring problem.

Quantum Generative Adversarial Network(qGAN)¶

qGAN is a hybrid quantum-classical algorithm used for generative modelling tasks. The qGAN implementation in Aqua requires the definition of a variational form for the implementation of a quantum generator and a PyTorch neural network for the implementation of a classical discriminator. These networks are trained in alternating optimization steps, where the discriminator tries to differentiate between training data samples and data samples from the generator and the generator aims at generating samples which the discriminator classifies as training data samples. Eventually, the quantum generator learns the training data’s underlying probability distribution. The trained quantum generator loads a quantum state which is a model of the target distribution.

For more details, please see this paper

In summary, qGAN can be configured with the following parameters:

An array indicating the numbers of qubits for d qubit registers, where d is dimension of the training data:

If no value for num_qubits is specified, the default is [3, 3, . 3] .

A positive int value configuring the batch size for batching the training data:

This has to be a positive int value. The default is 500 .

A positive int value configuring the number of training epochs:

This has to be a positive int value. The default is 3000 .

A positive int value configuring the seed for random values: .. code:: python

This has to be a positive int value. The default is 7 .

An optional positive float value for setting a tolerance for relative entropy. If the training results in a state such that the relative entropy is smaller or equal than the given tolerance the training will halt.

An optional str to give a directory where the parameters computed throughout the training shall be stored in CSV format.

When referring to qGAN declaratively inside Aqua, its code name , by which Aqua dynamically discovers and loads it is QGAN .

In Aqua, qGAN supports the distribution_learning_loading problem.


11.1: A- Jacobians, Inverses of Matrices, and Eigenvalues

This task view on numerical mathematics lists R packages and functions that are useful for solving numerical problems in linear algebra and analysis. It shows that R is a viable computing environment for implementing and applying numerical methods, also outside the realm of statistics.

The task view will não cover differential equations, optimization problems and solvers, or packages and functions operating on times series, because all these topics are treated extensively in the corresponding task views DifferentialEquations, Optimization, and TimeSeries. All these task views together will provide a good selection of what is available in R for the area of numerical mathematics. The HighPerformanceComputing task view with its many links for parallel computing may also be of interest.

The task view has been created to provide an overview of the topic. If some packages are missing or certain topics in numerical math should be treated in more detail, please let the maintainer know.

Numerical Linear Algebra

As statistics is based to a large extent on linear algebra, many numerical linear algebra routines are present in R, and some only implicitly. Examples of explicitly available functions are vector and matrix operations, matrix (QR) decompositions, solving linear equations, eigenvalues/-vectors, singular value decomposition, or least-squares approximation.

  • The recommended package Matrix provides classes and methods for dense and sparse matrices and operations on them, for example Cholesky and Schur decomposition, matrix exponential, or norms and conditional numbers for sparse matrices.
  • Recommended package MASS adds generalized (Penrose) inverses and null spaces of matrices.
  • expm computes the exponential, logarithm, and square root of square matrices, but also powers of matrices or the Frechet derivative. expm() is to be preferred to the function with the same name in Matrix.
  • SparseM provides classes and methods for sparse matrices and for solving linear and least-squares problems in sparse linear algebra
  • Package rmumps provides a wrapper for the MUMPS library, solving large linear systems of equations applying a parallel sparse direct solver
  • sanic supports routines for solving (dense and sparse) large systems of linear equations direct and iterative solvers from the Eigen C++ library are made available, including Cholesky, LU, QR, and Krylov subspace methods.
  • Rlinsolve is a collection of iterative solvers for sparse linear system of equations stationary iterative solvers such as Jacobi or Gauss-Seidel, as well as nonstationary (Krylov subspace) methods are provided.
  • svd provides R bindings to state-of-the-art implementations of singular value decomposition (SVD) and eigenvalue/eigenvector computations. Package ssvd will obtain sparse SVDs using an iterative thresholding method, while irlba will compute approximate singular values/vectors of large matrices.
  • Package PRIMME interfaces PRIMME, a C library for computing eigenvalues and eigenvectors of real symmetric or complex Hermitian matrices. It will find largest, smallest, or interior eigen-/singular values and will apply preconditioning to accelerate convergence.
  • The packages geigen and QZ compute generalized eigenvalues and -vectors for pairs of matrices, and QZ (generalized Schur) decompositions.
  • eigeninv generates matrices with a given set of eigenvalues ('inverse eigenvalue problem').
  • Package rARPACK, a wrapper for the ARPACK library, is typically used to compute only a few eigenvalues/vectors, e.g., a small number of largest eigenvalues.
  • Package RSpectra interfaces the 'Spectra' library for large-scale eigenvalue decomposition and SVD problems.
  • optR uses elementary methods of linear algebra (Gauss, LU, CGM, Cholesky) to solve linear systems.
  • Package mbend for bending non-positive-definite (symmetric) matrices to positive-definiteness, using weighted and unweighted methods.
  • matrixcalc contains a collection of functions for matrix calculations, special matrices, and tests for matrix properties, e.g., (semi-)positive definiteness mainly used for teaching and research purposes
  • matlib contains a collection of matrix functions for teaching and learning matrix linear algebra as used in multivariate statistical methods mainly for tutorial purposes in learning matrix algebra ideas using R.
  • Package onion contains routines for manipulating quaternions and octonians (normed division algebras over the real numbers) quaternions can be useful for handling rotations in three-dimensional space.
  • clifford provides a suite of routines for arbitrary dimensional Clifford algebras and discusses special cases such as Lorentz transforms or quaternion multiplication.
  • Packages RcppArmadillo and RcppEigen enable the integration of the C++ template libraries 'Armadillo' resp. 'Eigen' for linear algebra applications written in C++ and integrated in R using Rcpp for performance and ease of use.

Special Functions

Many special mathematical functions are present in R, especially logarithms and exponentials, trigonometric and hyperbolic functions, or Bessel and Gamma functions. Many more special functions are available in contributed packages.

  • Package gsl provides an interface to the 'GNU Scientific Library' that contains implementations of many special functions, for example the Airy and Bessel functions, elliptic and exponential integrals, the hypergeometric function, Lambert's W function, and many more.
  • Airy and Bessel functions, for real and complex numbers, are also computed in package Bessel, with approximations for large arguments.
  • Package pracma includes special functions, such as error functions and inverses, incomplete and complex gamma function, exponential and logarithmic integrals, Fresnel integrals, the polygamma and the Dirichlet and Riemann zeta functions.
  • The hypergeometric (and generalized hypergeometric) function, is computed in hypergeo, including transformation formulas and special values of the parameters.
  • HypergeoMat evaluates the hypergeometric functions of a matrix argument through a C++ implementation of Koev and Edelman's algorithm.
  • Elliptic and modular functions are available in package elliptic, including the Weierstrass P function and Jacobi's theta functions. There are tools for visualizing complex functions.
  • Carlson evaluates Carlson elliptic and incomplete elliptic integrals (with compex arguments).
  • Package expint wraps C-functions from the GNU Scientific Library to calculate exponential integrals and the incomplete Gamma function, including negative values for its first argument.
  • fourierin computes Fourier integrals of functions of one and two variables using the Fast Fourier Transform.
  • logOfGamma uses approximations to compute the natural logarithms of the Gamma function for large values.
  • Package lamW implements both real-valued branches of the Lambert W function (using Rcpp).

Polynomials

Function polyroot() in base R determines all zeros of a polynomial, based on the Jenkins-Traub algorithm. Linear regression function lm() can perform polynomial fitting when using poly() in the model formula (with option raw = TRUE).

  • Packages PolynomF (recommended) and polynom provide similar functionality for manipulating univariate polynomials, like evaluating polynomials (Horner scheme), or finding their roots. 'PolynomF' generates orthogonal polynomials and provides graphical display features.
  • polyMatrix (based on 'polynom') implements basic matrix operations and provides thus an infrastructure for the manipulation of polynomial matrices.
  • Package MonoPoly fits univariate polynomials to given data, applying different algorithms.
  • For multivariate polynomials, package multipol provides various tools to manipulate and combine these polynomials of several variables.
  • Package mpoly facilitates symbolic manipulations on multivariate polynomials, including basic differential calculus operations on polynomials, plus some Groebner basis calculations.
  • mvp enables fast manipulation of symbolic multivariate polynomials, using print and coercion methods from the 'mpoly' package, but offers speed improvements.
  • Package orthopolynom consists of a collection of functions to construct orthogonal polynomials and their recurrence relations, among them Chebyshev, Hermite, and Legendre polynomials, as well as spherical and ultraspherical polynomials. There are functions to operate on these polynomials.
  • Symbolic calculation and evaluation of the Jack polynomials, zonal polynomials (appear in random matrix theory), and Schur polynomials (appear in combinatorics) is available in package jack.
  • The Free Algebra in R package freealg handles multivariate polynomials with non-commuting indeterminates.

Differentiation and Integration

D() e deriv() in base R compute derivatives of simple expressions symbolically. Função integrate() implements an approach for numerically integrating univariate functions in R. It applies adaptive Gauss-Kronrod quadrature and can handle singularities and unbounded domains to a certain extent.

  • Package Deriv provides an extended solution for symbolic differentiation in R the user can add custom derivative rules, and the output for a function will be an executable function again.
  • numDeriv sets the standard for numerical differentiation in R, providing numerical gradients, Jacobians, and Hessians, computed by simple finite differences, Richardson extrapolation, or the highly accurate complex step approach.
  • Package dual achieves automatic differentiation (for univariate functions) by employing dual numbers for a mathematical function its value and its exact first derivative are returned.
  • Package autodiffr (on Github) provides an R wrapper for the Julia packages ForwardDiff.jl and ReverseDiff.jl to do automatic differentiation for native R functions.
  • pracma contains functions for computing numerical derivatives, including Richardson extrapolation or complex step. fderiv() computes numerical derivatives of higher orders. pracma has several routines for numerical integration: adaptive Lobatto quadrature, Romberg integration, Newton-Cotes formulas, Clenshaw-Curtis quadrature rules. integral2() integrates functions in two dimensions, also for domains characterized by polar coordinates or with variable interval limits.
  • Package gaussquad contains a collection of functions to perform Gaussian quadrature, among them Chebyshev, Hermite, Laguerre, and Legendre quadrature rules, explicitly returning nodes and weights in each case. Função gaussquad() in package statmod does a similar job.
  • Package fastGHQuad provides a fast Rcpp -based implementation of (adaptive) Gauss-Hermite quadrature.
  • Adaptive multivariate integration over hyper-rectangles in n-dimensional space is available in package cubature as function adaptIntegrate(), based on a C library of the same name. The integrand functions can even be multi-valued.
  • vegas() includes an approach to Monte Carlo integration based on importance sampling.
  • mvQuad provides methods for generating multivariate grids that can be used for multivariate integration. These grids will be based on different quadrature rules such as Newton-Cotes or Gauss quadrature formulas.
  • Package SparseGrid provides another approach to multivariate integration in high-dimensional spaces. It creates sparse n-dimensional grids that can be used as with quadrature rules.
  • Package SphericalCubature employs cubature to integrate functions over unit spheres and balls in n-dimensional space SimplicialCubature provides methods to integrate functions over m-dimensional simplices in n-dimensional space. Both packages comprise exact methods for polynomials.
  • Package polyCub holds some routines for numerical integration over polygonal domains in two dimensions.
  • Package Pade calculates the numerator and denominator coefficients of the Pade approximation, given the Taylor series coefficients of sufficient length.
  • calculus provides efficient functions for high-dimensional numerical and symbolic calculus, including accurate higher-order derivatives, Taylor series expansion, differential operators, and Monte-Carlo integration in orthogonal coordinate systems.
  • features extracts features from functional data, such as first and second derivatives, or curvature at critical points, while RootsExtremaInflections finds roots, extrema and inflection points of curves defined by discrete points.

Interpolation and Approximation

Base R provides functions approx() for constant and linear interpolation, and spline() for cubic (Hermite) spline interpolation, while smooth.spline() performs cubic spline approximation. Base package splines creates periodic interpolation splines in function periodicSpline().

  • Interpolation of irregularly spaced data is possible with the akima package: aspline() for univariate data, bicubic() ou interp() for data on a 2D rectangular domain. (This package is distributed under ACM license and not available for commercial use.)
  • Package signal contains several filters to smooth discrete data, notably interp1() for linear, spline, and cubic interpolation, pchip() for piecewise cubic Hermite interpolation, and sgolay() for Savitzky-Golay smoothing.
  • Package pracma provides barycentric Lagrange interpolation (in 1 and 2 dimensions) in barylag() resp. barylag2d(), 1-dim. akima in akimaInterp(), and interpolation and approximation of data with rational functions, i.e. in the presence of singularities, in ratinterp() e rationalfit().
  • The interp package provides bivariate data interpolation on regular and irregular grids, either linear or using splines. Currently the piecewise linear interpolation part is implemented. (It is intended to provide a free replacement for the ACM licensed akima::interp e tripack::tri.mesh functions.)
  • Package chebpol contains methods for creating multivariate Chebyshev and other multilinear interpolations on regular grids, e.g. the Floater-Hormann barycenter method, or polyharmonic splines for scattered data.
  • Package kubik provides (constructs, plots and evaluates) constrained cubic Hermite splines and computes their derivatives, indefinite integrals, as well as roots, optima, or inflection points.
  • tripack for triangulation of irregularly spaced data is a constrained two-dimensional Delaunay triangulation package providing both triangulation and generation of Voronoi mosaics of irregular spaced data.
  • sinterp() in package stinepack realizes interpolation based on piecewise rational functions by applying Stineman's algorithm. The interpolating function will be monotone in regions where the specified points change monotonically.
  • Schumaker() in package schumaker implements shape-preserving splines, guaranteed to be monotonic resp. concave or convex if the data is monotonic, concave, or convex.
  • ADPF uses least-squares polynomial regression and statistical testing to improve Savitzky-Golay smoothing.
  • Package conicfit provides several (geometric and algebraic) algorithms for fitting circles, ellipses, and conics in general.

Root Finding and Fixed Points

uniroot(), implementing the Brent-Decker algorithm, is the basic routine in R to find roots of univariate functions. There are implementations of the bisection algorithm in several contributed packages. For root finding with higher precision there is function unirootR() in the multi-precision package Rmpfr. And for finding roots of multivariate functions see the following packages:

  • Package rootSolve includes function multiroot() for finding roots of systems of nonlinear (and linear) equations it also contains an extension uniroot.all() that attempts to find all zeros of a univariate function in an intervall (excepting quadratic zeros).
  • For solving nonlinear systems of equations the BB package provides Barzilai-Borwein spectral methods in sane(), including a derivative-free variant in dfsane(), and multi-start features with sensitivity analysis.
  • Package nleqslv solves nonlinear systems of equations using alternatively the Broyden or Newton method, supported by strategies such as line searches or trust regions.
  • ktsolve defines a common interface for solving a set of equations with BB ou nleqslv.
  • Package daarem implements the DAAREM method for accelerating the convergence of any smooth, monotone, slow fixed point iteration.
  • Algorithms for accelerating the convergence of slow, monotone sequences from smooth contraction mappings such as the expectation-maximization (EM) algorithm are provided in packages SQUAREM resp. turboEM.

Discrete Mathematics and Number Theory

Not so many functions are available for computational number theory. Note that integers in double precision can be represented exactly up to 2^53 - 1, above that limit a multi-precision package such as gmp is needed, see below.

  • Package numbers provides functions for factorization, prime numbers, twin primes, primitive roots, modular inverses, extended GCD, etc. Included are some number-theoretic functions like divisor functions or Euler's Phi function.
  • contfrac contains various utilities for evaluating continued fractions and partial convergents.
  • magic creates and investigates magical squares and hypercubes, including functions for the manipulation and analysis of arbitrarily dimensioned arrays.
  • Package freegroup provides functionality for manipulating elements of a free group including juxtaposition, inversion, multiplication by a scalar, power operations, and Tietze forms.
  • The partitions package enumerates additive partitions of integers, including restricted and unequal partitions.
  • permutations treats permutations as invertible functions of finite sets and includes several mathematical operations on them.
  • Package combinat generates all permutations or all combinations of a certain length of a set of elements (i.e. a vector) it also computes binomial coefficients.
  • Package arrangements provides generators and iterators for permutations, combinations and partitions. The iterators allow users to generate arrangements in a fast and memory efficient manner. Permutations and combinations can be drawn with/without replacement and support multisets.
  • Package set6 implements (as R6 classes) many forms of mathematical sets (sets, tuples, intervals) and allows for standard operations on them (unions, products, differences).
  • RcppAlgos provides flexible functions for generating combinations or permutations of a vector with or without constraints the extension package RcppBigIntAlgos features a quadratic sieve algorithm for completely factoring large integers.
  • Package Zseq generates well-known integer sequences the 'gmp' package is adopted for computing with arbitrarily large numbers. Every function has on its help page a hyperlink to the corresponding entry in the On-Line Encyclopedia of Integer Sequences ( OEIS ).
  • Package primes provides quite fast (Rcpp) functions for identifying and generating prime numbers. And primefactr uses prime factorization for computations such as reducing ratios of large factorials.

Multi-Precision Arithmetic and Symbolic Mathematics

  • Multiple precision arithmetic is available in R through package gmp that interfaces to the GMP C library. Examples are factorization of integers, a probabilistic prime number test, or operations on big rationals -- for which linear systems of equations can be solved.
  • Multiple precision floating point operations and functions are provided through package Rmpfr using the MPFR and GMP libraries. Special numbers and some special functions are included, as well as routines for root finding, integration, and optimization in arbitrary precision.
  • Brobdingnag handles very large numbers by holding their logarithm plus a flag indicating their sign. (An excellent vignette explains how this is done using S4 methods.)
  • VeryLargeIntegers implements a multi-precision library that allows to store and manage arbitrarily big integers it includes probabilistic primality tests and factorization algorithms.
  • Package Ryacas interfaces the computer algebra system 'Yacas' it supports symbolic and arbitrary precision computations in calculus and linear algebra.
  • Packages caracas (based on 'reticulate') and rSymPy (based on 'rjava') both access the symbolic algebra system 'SymPy' supported are symbolic operations in linear algebra and calculus, such as eigenvalues, derivatives, integrals, limits, etc., computing special functions, or solving systems of equations.
  • Package symengine provides an interface to 'SymEngine', a C++ library for fast symbolic calculations, such as manipulating mathematical expressions, finding exact derivatives, performing symbolic matrix computations, or solving ordinary differential equations (numerically).

Python Interfaces

Python, through its modules 'NumPy', 'SciPy', 'Matplotlib', 'SymPy', and 'pandas', has elaborate and efficient numerical and graphical tools available.

  • reticulate is an R interface to Python modules, classes, and functions. When calling Python in R data types are automatically converted to their equivalent Python types when values are returned from Python to R they are converted back to R types. This package from the RStudio team is a kind of standard for calling Python from R.
  • feather provides bindings to read and write feather files, a lightweight binary data store designed for maximum speed. This storage format can also be accessed in Python, Julia, or Scala.
  • 'pyRserve' is a Python module for connecting Python to an R process running Rserve as an RPC gateway. This R process can run on a remote machine, variable access and function calls will be delegated through the network.
  • XRPython (and 'XRJulia') are based on John Chambers' XR package and his "Extending R" book and allow for a structured integration of R with Python resp. Julia.

MATLAB, Octave, Julia, and other Interfaces

Interfaces to numerical computation software such as MATLAB (commercial) or Octave (free) will be important when solving difficult numerical problems. Unfortunately, at the moment there is no package allowing to call Octave functions from within R.

  • The matlab emulation package contains about 30 simple functions, replicating MATLAB functions, using the respective MATLAB names and being implemented in pure R.
  • Packages rmatio and R.matlab provides tools to read and write MAT files (the MATLAB data format) for versions 4 and 5. 'R.matlab' also enables a one-directional interface with a MATLAB v6 process, sending and retrieving objects through a TCP connection.

Julia is "a high-level, high-performance dynamic programming language for numerical computing", which makes it interesting for optimization problems and other demanding scientific computations in R.

  • JuliaCall provides seamless integration between R and Julia the user can call Julia functions just like any R function, and R functions can be called in the Julia environment, both with reasonable automatic type conversion. Notes on Julia Call provides an introduction of how to apply Julia functions with 'JuliaCall'.
  • JuliaConnectoR provides a functionally oriented interface for integrating Julia with R imported Julia functions can be called as R functions data structures are converted automatically.
  • Package XRJulia provides an interface from R to computations in the Julia language, based on the interface structure described in the book "Extending R" by John M. Chambers.

Java Math functions can be employed through the 'rjava' or 'rscala' interfaces. Then package commonsMath allows calling Java JAR files of the Apache Commons Mathematics Library, a specialized library for all aspects of numerics, optimization, and differential equations.

SageMath is an open source mathematics system based on Python, allowing to run R functions, but also providing access to systems like Maxima, GAP, FLINT, and many more math programs. SageMath can be freely used through a Web interface at CoCalc .

Package m2r provides a persistent interface to Macauley2, an extended software program supporting research in algebraic geometry and commutative algebra. Macauley2 has to be installed independently, otherwise a Macauley2 process in the cloud will be instantiated.

Please note that commercial programs such as MATLAB, Maple, or Mathematica have facilities to call R functions.


Prelims Mathematics & Philosophy 2019-20

The synopses give some additional detail, and show how the material is split between the different lecture courses. They also include details of recommended reading.

The syllabus here is that referred to in the Examination Regulations 2019 Special Regulations for the Preliminary Examination in Mathematics & Philosophy (https://www.admin.ox.ac.uk/examregs/).

Mathematics I

Sets: examples including the natural numbers, the integers, the rational numbers, the real numbers inclusion, union, intersection, power set, ordered pairs and cartesian product of sets. Relations. Definition of an equivalence relation.

The well-ordering property of the natural numbers. Induction as a method of proof, including a proof of the binomial theorem with non-negative integral coefficients.

Maps: composition, restriction, injective (one-to-one), surjective (onto) and invertible maps, images and preimages.

Systems of linear equations. Matrices and the beginnings of matrix algebra. Use of matrices to describe systems of linear equations.
Elementary Row Operations (EROs) on matrices. Reduction of matrices to echelon form. Application to the solution of systems of linear equations.

Inverse of a square matrix. Reduced row echelon (RRE) form and the use of EROs to compute inverses computational efficiency of the method. Transpose of a matrix orthogonal matrices.

Vector spaces: definition of a vector space over a field (such as $mathbb$, $mathbb$, $mathbb$). Subspaces. Many explicit examples of vector spaces and subspaces.

Span of a set of vectors. Examples such as row space and column space of a matrix. Linear dependence and independence. Bases of vector spaces examples. The Steinitz Exchange Lemma dimension. Application to matrices: row space and column space, row rank and column rank. Coordinates associated with a basis of a vector space.

Use of EROs to find bases of subspaces. Sums and intersections of subspaces the dimension formula. Direct sums of subspaces.

Linear transformations: definition and examples (including projections associated with direct-sum decompositions). Some algebra of linear transformations inverses. Kernel and image, Rank-Nullity Theorem. Applications including algebraic characterisation of projections (as idempotent linear transformations).

Matrix of a linear transformation with respect to bases. Change of Bases Theorem. Applications including proof that row rank and column rank of a matrix are equal.

Bilinear forms real inner product spaces examples. Mention of complex inner product spaces. Cauchy--Schwarz inequality. Distance and angle. The importance of orthogonal matrices.

Introduction to determinant of a square matrix: existence and uniqueness and relation to volume. Proof of existence by induction. Basic properties, computation by row operations.

Determinants and linear transformations: multiplicativity of the determinant, definition of the determinant of a linear transformation. Invertibility and the determinant. Permutation matrices and explicit formula for the determinant deduced from properties of determinant.

Eigenvectors and eigenvalues, the characteristic polynomial. Trace. Proof that eigenspaces form a direct sum. Examples. Discussion of diagonalisation. Geometric and algebraic multiplicity of eigenvalues.

Spectral theorem for real symmetric matrices. Matrix realisation of bilinear maps given a basis and application to orthogonal transformation of quadrics into normal form. Statement of classification of orthogonal transformations.

Axioms for a group and for an Abelian group. Examples including geometric symmetry groups, matrix groups ($GL_$, $SL_$, $O_$, $ SO_$, $U_$), cyclic groups. Products of groups.

Permutations of a finite set under composition. Cycles and cycle notation. Order. Transpositions every permutation may be expressed as a product of transpositions. The parity of a permutation is well-defined via determinants. Conjugacy in permutation groups.

Subgroups examples. Intersections. The subgroup generated by a subset of a group. A subgroup of a cyclic group is cyclic. Connection with hcf and lcm. Bezout's Lemma.

Recap on equivalence relations including congruence mod n and conjugacy in a group. Proof that equivalence classes partition a set. Cosets and Lagrange's Theorem examples. The order of an element. Fermat's Little Theorem.

Isomorphisms, examples. Groups of order 8 or less up to isomorphism (stated without proof). Homomorphisms of groups with motivating examples. Kernels. Images. Normal subgroups. Quotient groups examples. First Isomorphism Theorem. Simple examples determining all homomorphisms between groups.

Group actions examples. Definition of orbits and stabilizers. Transitivity. Orbits partition the set. Stabilizers are subgroups.

Orbit-stabilizer Theorem. Examples and applications including Cauchy's Theorem and to conjugacy classes.

Orbit-counting formula. Examples.

The representation $G ightarrow mathrm(S)$ associated with an action of $G$ on $S$. Cayley's Theorem. Symmetry groups of the tetrahedron and cube.

Mathematics II

Real numbers: arithmetic, ordering, suprema, infima real numbers as a complete ordered field. Countable sets. The rational numbers are countable. The real numbers are uncountable.

The complex number system. The Argand diagram modulus and argument. De Moivre's Theorem, polar form, the triangle inequality. Statement of the Fundamental Theorem of Algebra. Roots of unity. Simple transformations in the complex plane. Polar form, with applications.

Sequences of (real or complex) numbers. Limits of sequences of numbers the algebra of limits. Order notation.

Subsequences every subsequence of a convergent sequence converges to the same limit. Bounded monotone sequences converge. Bolzano-Weierstrass Theorem. Cauchy's convergence criterion. Limit point of a subset of the line or plane.

Series of (real or complex) numbers. Convergence of series. Simple examples to include geometric progressions and power series. Alternating series test, absolute convergence, comparison test, ratio test, integral test.

Power series, radius of convergence, important examples to include definitions of relationships between exponential, trigonometric functions and hyperbolic functions.

Continuous functions of a single real or complex variable. Definition of continuity of real valued functions of several variables.

The algebra of continuous functions. A continuous real-valued function on a closed bounded interval is bounded, achieves its bounds and is uniformly continuous. Intermediate Value Theorem. Inverse Function Theorem for continuous strictly monotonic functions.

Sequences and series of functions. The uniform limit of a sequence of continuous functions is continuous. Weierstrass's M-test. Continuity of functions defined by power series.

Definition of derivative of a function of a single real variable. The algebra of differentiable functions. Rolle's Theorem. Mean Value Theorem. Cauchy's (Generalized) Mean Value Theorem. L'Hôpital's Formula. Taylor's expansion with remainder in Lagrange's form. Binomial theorem with arbitrary index.

Step functions and their integrals. The integral of a continuous function on a closed bounded interval. Properties of the integral including linearity and the interchange of integral and limit for a uniform limit of continuous functions on a bounded interval. The Mean Value Theorem for Integrals. The Fundamental Theorem of Calculus integration by parts and substitution.

Term-by-term differentiation of a (real) power series (interchanging limit and derivative for a series of functions where the derivatives converge uniformly).

Mathematics III(P)

General linear homogeneous ODEs: integrating factor for first order linear ODEs, second solution when one solution is known for second order linear ODEs. First and second order linear ODEs with constant coefficients. General solution of linear inhomogeneous ODE as particular solution plus solution of homogeneous equation. Simple examples of finding particular integrals by guesswork.

Partial derivatives. Second order derivatives and statement of condition for equality of mixed partial derivatives. Chain rule, change of variable, including planar polar coordinates. Solving some simple partial differential equations (e.g. $f_ = 0$, $f_x = f_y$).

Parametric representation of curves, tangents. Arc length. Line integrals.

Jacobians with examples including plane polar coordinates. Some simple double integrals calculating area and also $int_^2> e^ <-(x^2+y^2)>dA$.

Simple examples of surfaces, especially as level sets. Gradient vector normal to surface directional derivative $int^B_A abla phi cdot dmathbf = phi(B)-phi(A)$.

Taylor's Theorem for a function of two variables (statement only). Critical points and classification using directional derivatives and Taylor's theorem. Informal (geometrical) treatment of Lagrange multipliers.

Sample space, algebra of events, probability measure. Permutations and combinations, sampling with or without replacement. Conditional probability, partitions of the sample space, theorem of total probability, Bayes' Theorem. Independence.

Discrete random variables, probability mass functions, examples: Bernoulli, binomial, Poisson, geometric. Expectation: mean and variance. Joint distributions of several discrete random variables. Marginal and conditional distributions. Independence. Conditional expectation, theorem of total probability for expectations. Expectations of functions of more than one discrete random variable, covariance, variance of a sum of dependent discrete random variables.

Solution of first and second order linear difference equations. Random walks (finite state space only).

Probability generating functions, use in calculating expectations. Random sample, sums of independent random variables, random sums. Chebyshev's inequality, Weak Law of Large Numbers.

Continuous random variables, cumulative distribution functions, probability density functions, examples: uniform, exponential, gamma, normal. Expectation: mean and variance. Functions of a single continuous random variable. Joint probability density functions of several continuous random variables (rectangular regions only). Marginal distributions. Independence. Expectations of functions of jointly continuous random variables, covariance, variance of a sum of dependent jointly continuous random variables.


Appendix.: Methods

Two main methods were used. The first used an analytical approach, while the second used a numerical approach. The first method was used on models 1 to 4, and on models 5 and 6 for n = 1–6. In these cases the number of samples used was 100 000. O segundo método foi usado no modelo 5 e 6 para n = 1–10 e n = 20, 30. 100, desta vez, por razões computacionais, o tamanho da amostra foi de 1.000.

A.1. O método analítico

Para cada um dos modelos, os EPs foram encontrados usando o solucionador de equações analíticas do Matlab, resolver. O Jacobiano também foi descrito analiticamente usando o Matlab's jacobiano função.

Os diferentes parâmetros foram amostrados a partir de uma distribuição uniforme usando o Matlab rand função. A escolha da faixa dos parâmetros será descrita em detalhes a seguir.

A.1.1. Algoritmo

Para cada um dos modelos, os EPs e sua estabilidade para uma gama diferente de parâmetros são avaliados da seguinte maneira.


Assista o vídeo: Rápido e Fácil. Matriz Inversa (Outubro 2021).