¿Cómo calculo el $p$-norma de una matriz?

Question

Sé que la $p$-norma de una matriz es:

$$\|A\| = \max_{x\neq 0} \frac{\|Ax\|_p}{\|x\|_p}$$

pero no saben lo que esto realmente significa.

Cómo puedo calcular el $2$-norma, $3$-norm, etc. para la matriz.

$$A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$$

Actualización Al parecer, la matriz anterior es demasiado fácil :) Vamos a intentar algo más difícil.

$$A = \begin{bmatrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{bmatrix}$$

Gracias,

Answer 1

Como he mencionado en esta respuesta a un MO pregunta, Nick Higham ha hecho que la nota de un numérica método que él atribuye a Boyd para estimar el $p$-norma de una matriz, la cual es esencialmente un aproximado de maximización esquema similar en sabor a la habitual método de la potencia para calcular el autovalor dominante; Higham el libro tiene un par de detalles, su artículo un poco más, y luego ver esta implementación en MATLAB del algoritmo.

---

Código? Por qué seguro! He aquí un Mathematica traducción de la rutina de MATLAB pnorm():

dualVector[vec_?VectorQ, p_] := 
 Module[{q = If[p == 1, Infinity, 1/(1 - 1/p)], n = Length[vec]}, 
   If[Norm[vec, Infinity] == 0, Return[vec]];
   Switch[p,
    1, 2 UnitStep[vec] - 1,
    Infinity, (Sign[Extract[vec, #]] UnitVector[n, #]) &[
     First[Flatten[Position[Abs[vec], Max[Abs[vec]]]]]],
    _, Normalize[(2 UnitStep[vec] - 1) Abs[
        Normalize[vec, Norm[#, Infinity] &]]^(p - 1), 
     Norm[#, q] &]]] /; p >= 1

Options[pnorm] = {"Samples" -> 9, Tolerance -> Automatic};

pnorm[mat_?MatrixQ, p_, opts___] := 
 Module[{q = If[p == 1, Infinity, 1/(1 - 1/p)], m, n, A, tol, sm, x, 
    y, c, s, W, fo, f, c1, s1, est, eo, z, k, th},
   {m, n} = Dimensions[mat];
   A = If[Precision[mat] === Infinity, N[mat], mat];
   {sm, tol} = {"Samples", Tolerance} /. {opts} /. Options[pnorm];
   If[tol === Automatic, tol = 10^(-Precision[A]/3)];
   y = Table[0, {m}]; x = Table[0, {n}];
   Do[
    If[k == 1, {c, s} = {1, 0},
     W = Transpose[{A[[All, k]], y}];
     fo = 0;
     Do[
      {c1, s1} = Normalize[Through[{Cos, Sin}[th]], Norm[#, p] &];
      f = Norm[W.{c1, s1}, p];
      If[f > fo,
       fo = f; {c, s} = {c1, s1}];
      , {th, 0, Pi, Pi/(sm - 1)}]
     ];
    x[[k]] = c;
    y = c A[[All, k]] + s y;
    If[k > 1, x = Join[s Take[x, k - 1], Drop[x, k - 1]]];
    , {k, n}];
   est = Norm[y, p];
   For[k = 1, True, k++,
    y = A.x;
    eo = est; est = Norm[y, p];
    z = Transpose[A].dualVector[y, p];
    If[(Norm[z, q] < z.x || Abs[est - eo] <= tol est) && k > 1, 
     Break[]];
    x = dualVector[z, q];];
   est] /; p >= 1

Ahora, vamos a usar el OP de la matriz como un ejemplo:

mat = N[{{2, 1, 4}, {3, 0, -1}, {1, 1, 2}}];

y ver lo bueno que el estimador es en los casos conocidos:

(pnorm[ma, #] - Norm[ma, #]) & /@ {1, 2, Infinity} // InputForm
{0., -2.2045227554556845*^-6, 0.}

(es decir, la estimación de la 2-norma es bueno ~ 5 dígitos; ajustando Samples, Tolerance, o ambos daría mejores resultados).

Vamos a comparar con Robert ejemplo:

pnorm[ma, 4, Tolerance -> 10^-9] // InputForm
5.695759123950937

Muy cerca!

Finalmente, aquí está una parcela de la $p$-norma de la OP matriz con diferentes $p$:

Answer 2

CRÉDITO EXTRA: encontrar los valores propios, vectores propios, y el $1,2,\infty$ normas de la matriz $$B = \begin{pmatrix} 1 & 10 \\ -16 & 9 \end{pmatrix},$$ el uso de los métodos se ilustra a continuación. He organizado para que todo funcione bien.

ORIGINAL: nunca he visto a estos calculado, excepto para $p=1,2,\infty.$ Tenga en cuenta que la 1 de la norma de un vector es la suma de los valores absolutos de las entradas, mientras que el $\infty$ norma de un vector es el mayor valor absoluto de cualquier entrada.

Como se puede ver en el enlace dado por Jonas, el $\infty$ norma es la más grande de fila suma(valores absolutos), que para su 3 por 3 ejemplo es 2 + 1 + 4 = 7. Esto se logra por un vector columna que consta de todos los $\pm 1,$, donde la elección de $\pm$ está hecho de manera que el producto con el $2,1,4$ son todas positivas, por lo que en este caso todos los $+1. $ De su matriz $$A = \left[\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right],$$

$$A = \left(\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right) \cdot \left(\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right) = \left(\begin{matrix} 7 \\ 2 \\ 4 \end{matrix}\right), $$ así que con $$ x = \left(\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right), $$ tenemos $$ \|x\|_\infty = 1, \; \; \|Ax\|_\infty = 7, \; \; \frac{ \|Ax\|_\infty}{\|x\|_\infty} = 7, $$ y $$ \|A\|_\infty = 7. $$

The $1$ la norma es la más grande de la columna suma(valores absolutos), que para su 3 por 3 ejemplo es 4 + 1 + 2 = 7. Esto se logra por un vector columna que consta de casi todos 0 y 1, donde la elección de la posición de la 1 se hace para que los más importante de la columna se mantiene. Tome su matriz $$A = \left[\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right],$$

$$A = \left(\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right) \cdot \left(\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}\right) = \left(\begin{matrix} 4 \\ -1 \\ 2 \end{matrix}\right), $$ así que con $$ x = \left(\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}\right), $$ tenemos $$ \|x\|_1 = 1, \; \; \|Ax\|_1 = 7, \; \; \frac{ \|Ax\|_1}{\|x\|_1} = 7, $$ y $$ \|A\|_1 = 7. $$

Éstas dan a los límites superiores de las normas de autovalores, trabajando en eso. De GP-Pari, el mayor autovalor es de aproximadamente 4.7,

? mat = [2,1,4; 3,0,-1; 1,1,2]
%1 = 
[2 1 4]

[3 0 -1]

[1 1 2]

? charpoly(mat)
%2 = x^3 - 4*x^2 - 2*x - 7
? 
? matdet(mat)
%3 = 7
? 
? polroots(  charpoly(mat)  )
%4 = [4.734676178725887352610775374 ,
 -0.3673380893629436763053876869 - 1.159101604948420124760141070*I,
 -0.3673380893629436763053876869 + 1.159101604948420124760141070*I]~
? 

Voy a conseguir, el autovector por la real autovalor es dada numéricamente como $$ x = \left(\begin{matrix} 1.803282495304177184832508716 \\ 0.9313936834217101677782666577 \\ 1 \end{matrix}\right), $$

? vec = [  1.803282495304177184832508716 , 0.9313936834217101677782666577, 1   ]
%7 = [1.803282495304177184832508716, 0.9313936834217101677782666577, 1]

? columnvec = mattranspose( vec)
%8 = [1.803282495304177184832508716, 0.9313936834217101677782666577, 1]~
? mat * columnvec
%9 = [8.537958674030064537443284089, 4.409847485912531554497526148, 4.734676178725887352610775374]~
? mat * columnvec  -   4.734676178725887352610775374  * columnvec
%10 = [4.038967835 E-28, -7.068193710 E-28, -4.038967835 E-28]~
? 

Answer 3

Para otros valores de $p$, puede utilizar métodos de multiplicador de Lagrange. Aquí, por ejemplo, es su ejemplo $3 \times 3$ $p=4$ utilizando arce.

> M:= <<2|1|4>,<3|0|-1>,<1|1|2>>;
  X:= <x1,x2,x3>;
  MX:= M.X;
  F:= add(MX[i]^4,i=1..3)-lambda*(add(X[i]^4,i=1..3)-1);
  eqs:= {diff(F,x1),diff(F,x2),diff(F,x3),diff(F,lambda)};
  S:=RootFinding[Isolate](eqs,[x1,x2,x3,lambda]);
  pnorm:= max(map(t -> eval(lambda,t),S))^(1/4);

pnorm: = 5.695759124