|
"Hydroman S" <amirgsalem@gmail.com> wrote in message <ggl978$1mk$1@fred.mathworks.com>...
> Is it true then that there is no way arround doing the division on the full size of b & A without using " inv ". My goal was to reduce the size of b and A to get the x elment of interst.
>
> It might also be worth it to share the reason why I'm trying to do this in case someone has any sugesstions:
>
> I'm solving a system of the form Ax=b --------> x = b \ A
>
> x is 6 x1 , A is 6 x 6 & b is 6 x 1.
> A is also a function of x, so my solution involves a simple iteration over x = b \ A , i.e.
> x(n+1) = b \ A(x(n))
>
> I want to perform the iteration over A(5,:) , b(5,:) instead of iterating arround the whole system, the result of interst is x(5,:) . I don't want to use Newton method or fsolve for my solution.....
>
> I really appreciate all your help and suggestions.
Bruno is correct, so I'll just expand a bit on what
he said, though I'll add an option if you are willing
to potentially lose some accuracy.
You are solving a linear system of equations. Unless
A has some special property (an example of such a
special property would be if A was a A block diagonal
matrix, or something morally equivalent to one) you
cannot just drop some of the information from that
linear system and solve it.
The idea that you could use only one row of A here is
equivalent to starting with a system of linear equations,
but then throwing away all of the coefficients in all of
your equations except for the coefficients that involve
the variable x(5). They call it a system of equations
for a reason. It is a system, and it must stay that way.
Newton's method or fsolve would be completely silly
here. It would be the equivalent of the use of a Mack
truck to carry a pea to Boston. Why use a nonlinear
iterative scheme to solve a linear problem, especially
when it will actually call \ internally anyway?
Having said all of that, there are ways where one
can solve a linear system for one of the variables,
doing less work than might backslash or slash does.
You are trying to solve the problem
x*A = b
where A is 6x6, but you only care about x(5). First
of all, reorder the unknowns, so that you will only
compute the last one. (Unfortunately, what I am
doing may significantly reduce the accuracy of your
solution if A is anywhere close to being singular.)
The idea I'll use is to compute a NON-pivoted LQ
decomposition of A. So if
A = Q*L
then we can write the problem as
x*L = b*Q'
Here L is a lower triangular matrix. Normally, we
would finish solving the problem using
x = (b*Q')/L
and MATLAB is smart enough to know that since L
is lower triangular, then it can use a simple scheme
(back substitution) to solve it. This last part is a
fast thing to do, only O(n^2) ops, compared to the
O(n^3) ops required for the decomposition itself.
Since you already know that information, and you
only want the last element of x, we can short circuit
the last part of the solution.
How would you do this in MATLAB? MATLAB does
not have a built-in LQ factorization. But it does have
a QR. We can use those factors for our purpose.
format long g
[Q,R] = qr(A');
x6 = (b*Q(:,6))/R(6,6);
Verify that this worked in an example:
b = randn(1,6);
A = randn(6);
% Solve for just x(6) as above.
[Q,R] = qr(A');
x6 = (b*Q(:,6))/R(6,6)
x6 =
0.125469006067183
Was it correct? Compare to the complete solution
using slash.
(b/A)'
ans =
-0.486154697459952
-0.613860483571218
-0.301297492056063
0.0744768344805876
-0.626607248909288
0.125469006067182
See that the last element is the same, at least to within
most of its few digits. Had A been nearly singular, the
use of a non-pivoted QR might have been more costly.
More importantly, does this save us any time? Write it
as a function so I can best compare the time required.
function x6 = testfun(A,b)
[Q,R] = qr(A');
x6 = (b*Q(:,6))/R(6,6);
Now, do some timing comparisons:
timeit(@() testfun(A,b))
ans =
0.000171779387440118
timeit(@() (b/A)*[0 0 0 0 0 1]')
ans =
0.000154544676339716
Even with a multiplication at the end to pick out
only the last element of x, the slash solution is still
faster! And remember, / will be more accurate when
A is poorly conditioned. Since A is really a function
of another parameter, it could easily temporarily
become nearly singular along the way.
So, can you reduce the work required to solve a 6x6
linear system? Yes you can, but you still won't save
any time, and you will lose some stability in the
solution because we had to use the unpivoted
QR decomposition.
Buy a faster computer, go get a cup of coffee, put
your feet up on the desk, and read a good book
while you wait.
John
|
Feed for this Thread