Root finding procedure?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Root finding procedure?

Thomas Hoffmann-3
I am looking for octave- or matlab-code, that allows me to find the
roots of the polynomial of x that results from det(H)=0, where the Hij
are polynomials in x theirself.
E.g.: find the roots x for

       3x-4    2x+9
det (                 ) = 0
       -x+22   4x-11

I can program such a procedure myself (with successive convolution),
but this problem seems standard enough to me, that there could be a
procedure out there in octave-land.
Any hints?

Thomas Hoffmann.


Reply | Threaded
Open this post in threaded view
|

Re: Root finding procedure?

Heber Farnsworth-2
The thing that comes to mind is fsolve.  Write a m-file which takes x as
an argument and return det(H).  Use fsolve and it will return the value
of x that makes det(H) as close to zero as possible.  Of course there
will be a problem with multiple roots and so the answer you get will
depend on the starting value you give to fsolve.  I don't know of one
that returns all the roots.

On Fri, 4 Jul 1997, Thomas Hoffmann wrote:

> I am looking for octave- or matlab-code, that allows me to find the
> roots of the polynomial of x that results from det(H)=0, where the Hij
> are polynomials in x theirself.
> E.g.: find the roots x for
>
>        3x-4    2x+9
> det (                 ) = 0
>        -x+22   4x-11
>
> I can program such a procedure myself (with successive convolution),
> but this problem seems standard enough to me, that there could be a
> procedure out there in octave-land.
> Any hints?
>
> Thomas Hoffmann.
>


Reply | Threaded
Open this post in threaded view
|

Re: Root finding procedure?

"Jack A Walker/BII"
In reply to this post by Thomas Hoffmann-3

  Matlab's root finder for polynomials finds the eigen values of the
  companion matrix of the polynomial.  In a way sort of ironic.

  Jack





                   help-octave @ bevo.che.wisc.edu at INTERNET
                   07/05/97 10:18 AM





  To:   hoffmann @ ehmgs2.et.tu-dresden.de at INTERNET@CCMAIL
  cc:   help-octave @ bevo.che.wisc.edu at INTERNET@CCMAIL, farnswor @
        cob.ohio-state.edu at INTERNET@CCMAIL (bcc: Jack A Walker/BII)
  Subject:  Re: Root finding procedure?


The thing that comes to mind is fsolve.  Write a m-file which takes x as
an argument and return det(H).  Use fsolve and it will return the value
of x that makes det(H) as close to zero as possible.  Of course there
will be a problem with multiple roots and so the answer you get will
depend on the starting value you give to fsolve.  I don't know of one
that returns all the roots.

On Fri, 4 Jul 1997, Thomas Hoffmann wrote:

> I am looking for octave- or matlab-code, that allows me to find the
> roots of the polynomial of x that results from det(H)=0, where the Hij
> are polynomials in x theirself.
> E.g.: find the roots x for
>
>        3x-4    2x+9
> det (                 ) = 0
>        -x+22   4x-11
>
> I can program such a procedure myself (with successive convolution),
> but this problem seems standard enough to me, that there could be a
> procedure out there in octave-land.
> Any hints?
>
> Thomas Hoffmann.
>

(See attached file: RFC822.TXT)

Received: from bevo.che.wisc.edu by ccgate.dp.beckman.com (SMTPLINK V2.11 PreRelease 4)
    ; Sat, 05 Jul 97 10:17:49 pst
Return-Path: <[hidden email]>
Received: from localhost (daemon@localhost) by bevo.che.wisc.edu (8.6.12/8.6.12) with SMTP id MAA16149; Sat, 5 Jul 1997 12:14:09 -0500
Received: by bevo.che.wisc.edu (bulk-mailer v1.3); Sat, 5 Jul 1997 12:12:36 -0500
Received: (from slist@localhost) by bevo.che.wisc.edu (8.6.12/8.6.12) id MAA16088 for [hidden email]; Sat, 5 Jul 1997 12:12:34 -0500
Resent-Date: Sat, 5 Jul 1997 12:12:34 -0500
Date: Sat, 5 Jul 1997 13:12:26 -0400 (EDT)
From: Heber Farnsworth <[hidden email]>
Subject: Re: Root finding procedure?
To: Thomas Hoffmann <[hidden email]>
cc: [hidden email]
In-Reply-To: <[hidden email]>
Message-ID: <Pine.3.89.9707051324.A6118-0100000@quest>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Resent-Message-ID: <"gizbI9s5FqB.A.V7D.CCovz"@bevo.che.wisc.edu>
Resent-From: [hidden email]
X-Mailing-List: <[hidden email]>
X-Loop: [hidden email]
Resent-Sender: [hidden email]


Reply | Threaded
Open this post in threaded view
|

Re: Root finding procedure?

Ole Myren R|hne
On Fri, 4 Jul 1997, Thomas Hoffmann wrote:

> I am looking for octave- or matlab-code, that allows me to find the
> roots of the polynomial of x that results from det(H)=0, where the Hij
> are polynomials in x theirself.
> E.g.: find the roots x for
>
>        3x-4    2x+9
> det (                 ) = 0
>        -x+22   4x-11
>

I don't know if this is of any use:

If your Hij polynomials are indeed *first order*, it should be possible
to cast your problem in the form of a generalized eigenvalue problem:

        Ay = x By (B=1 gives simple eigenvalue problem)

If B has an inverse C (CB = 1) this is equivalent to the simple
eigenvalue problem

       CAy = x y

In your simple example,

    (-4   9)
A = (22 -11)

    ( 3   2)
B =-(-1   4)

AFAIK, EISPACK and/or LAPACK have routines that solve the generalized
eigenvalue problem. I don't know if any such routine is interfaced to
octave, but writing the glue code should be easy.

If your Hij are not *first order*, it seems to me that the trick could
still work, but the matrix dimension will increase.

        Regards,

        Ole